Merge Two Sorted Linked Lists in DSA C - Time & Space Complexity

Time Complexity: Merge Two Sorted Linked Lists

O(n)

Understanding Time Complexity

We want to know how the time needed to merge two sorted linked lists changes as the lists get bigger.

Specifically, how does the number of steps grow when the input lists grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}
    

This code merges two sorted linked lists by comparing their nodes and building a new sorted list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing nodes from both lists and moving forward one node at a time.
• How many times: Each node from both lists is visited exactly once during the merge.

How Execution Grows With Input

As the total number of nodes in both lists grows, the number of comparisons grows roughly the same amount.

Input Size (n = total nodes)	Approx. Operations
10	About 10 comparisons
100	About 100 comparisons
1000	About 1000 comparisons

Pattern observation: The number of steps grows linearly with the total number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to merge grows directly in proportion to the total number of nodes in both lists.

Common Mistake

[X] Wrong: "The merge takes quadratic time because it compares nodes multiple times."

[OK] Correct: Each node is visited only once, so comparisons happen once per node, not repeatedly.

Interview Connect

Understanding this linear time merge is a key skill for working with linked lists and sorting algorithms.

Self-Check

"What if the input lists were not sorted? How would the time complexity of merging change?"