Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Additional information

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Example 1:

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]

Output: [1, 1, 2, 3, 4, 4]

Explanation: The nodes are merged in increasing order: 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

Input: list1 = [], list2 = [0]

Output: [0]

Brute Force (Collect & Sort)

Intuition

Since a Linked List is hard to manipulate directly for sorting, the naive approach is to extract all values from both linked lists into a standard Python list (array). We then sort this array and construct a completely new Linked List from the sorted values.

Algorithm

1. Traverse list1 and append all values to a list vals.

2. Traverse list2 and append all values to vals.

3. Sort vals.

4. Create a dummy node dummy.

5. Iterate through vals, creating a new ListNode for each value and attaching it to the current chain.

6. Return dummy.next.

def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    vals = []
    
    # Collect values
    curr = list1
    while curr:
        vals.append(curr.val)
        curr = curr.next
    
    curr = list2
    while curr:
        vals.append(curr.val)
        curr = curr.next
        
    # Sort
    vals.sort()
    
    # Build new list
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
        
    return dummy.next

Time & Space Complexity

• Time complexity: O(N \log N)
  • Reason: Sorting the list of values takes O(N \log N), where N is the total number of nodes.
• Space complexity: O(N)
  • Reason: We store all values in a list and create a new Linked List.

Iterative Two Pointers (Optimal)

Intuition

Since both lists are already sorted, we don't need to re-sort everything. We can use the Two Pointer technique (similar to the merge step in Merge Sort).

We traverse both lists simultaneously. At each step, we compare the current node of list1 and list2. We attach the smaller node to our result list and move that pointer forward. This "stitches" the existing nodes together without needing extra space for values.

Algorithm

1. Create a dummy node to act as the start of the result list.

2. Initialize tail to dummy.

3. While both list1 and list2 are not None:

   • If list1.val < list2.val:

     • Attach list1 to tail.next.

     • Move list1 forward.

   • Else:

     • Attach list2 to tail.next.

     • Move list2 forward.

   • Move tail forward.

4. One list will be exhausted before the other. Attach the remaining non-empty list to tail.next.

5. Return dummy.next.

def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    tail = dummy
    
    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
        
    # Attach the remaining part of the list that isn't empty
    if list1:
        tail.next = list1
    elif list2:
        tail.next = list2
        
    return dummy.next

Time & Space Complexity

• Time complexity: O(n + m)
  • Reason: We iterate through both lists exactly once.
• Space complexity: O(1)
  • Reason: We only use a few pointers (dummy, tail) and rearrange existing nodes.