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

Time Complexity: Merge Two Sorted Linked Lists

O(n + m)

Understanding Time Complexity

When merging two sorted linked lists, we want to know how the time needed grows as the lists get longer.

We ask: How many steps does it take to combine both lists into one sorted list?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next
    

This code merges two sorted linked lists by repeatedly choosing the smaller head node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares nodes from both lists.
• How many times: It runs until all nodes from both lists are processed, so roughly the total number of nodes combined.

How Execution Grows With Input

As the total number of nodes increases, the steps to merge grow roughly the same amount.

Input Size (total nodes)	Approx. Operations
10	About 10 comparisons and moves
100	About 100 comparisons and moves
1000	About 1000 comparisons and moves

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

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows in direct proportion to the total number of nodes in both lists combined.

Common Mistake

[X] Wrong: "Merging two lists takes O(n * m) time because of nested comparisons."

[OK] Correct: The code only compares one node from each list at a time, moving forward without going back, so it never repeats work for the same nodes.

Interview Connect

Understanding this linear merging process shows you can handle combining sorted data efficiently, a key skill in many coding problems.

Self-Check

"What if the input lists were stored as arrays instead of linked lists? How would the time complexity change?"