Editorial: Merge Two Sorted Lists

Overview

The problem asks us to combine two singly linked lists that are already sorted in non-decreasing order into a single, merged linked list. The resulting list must also be sorted.

The most intuitive way to approach linked list problems is to imagine traversing them step by step. Since both input lists are already sorted, the smallest overall element must be at the head of either list1 or list2. If we can continuously compare the current nodes of both lists, pick the smaller one, and append it to our result, we can build the merged list efficiently.

Brute force

If we momentarily ignore the fact that the two input lists are already sorted, the most straightforward (naive) approach is to extract all the values from both linked lists into a standard array. Once all values are in the array, we can sort it, and then build an entirely new linked list from the sorted values.

While this approach is guaranteed to yield a correct, sorted linked list, it fails to leverage the pre-sorted nature of the inputs and wastes both time and memory.

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

def merge_two_sorted_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    values = []
    
    # 1. Extract values from the first list
    curr1 = list1
    while curr1:
        values.append(curr1.val)
        curr1 = curr1.next
        
    # 2. Extract values from the second list
    curr2 = list2
    while curr2:
        values.append(curr2.val)
        curr2 = curr2.next
        
    # 3. Sort the combined array
    values.sort()
    
    # 4. Build a new linked list from the sorted array
    dummy = ListNode(-1)
    curr = dummy
    for val in values:
        curr.next = ListNode(val)
        curr = curr.next
        
    return dummy.next

• Time complexity: O((N + M) log(N + M)) — Extracting the N + M nodes takes linear time, but sorting the combined array dominates the runtime.
• Space complexity: O(N + M) — We store all values from both lists in an external array and allocate entirely new ListNode objects to create the result.

Optimal / best approach

To optimize this, we should take advantage of the fact that list1 and list2 are already sorted. This allows us to use a Two-Pointer technique, moving through both lists simultaneously.

We can create a dummy node to act as the starting point of our merged list. This is a common linked list trick that helps us easily handle edge cases (like when one or both input lists are initially empty) without needing complex initialization logic. We also use a curr pointer to keep track of the tail of our newly merged list.

We will iterate as long as both list1 and list2 have unvisited nodes:

1. Compare the values of the current nodes in list1 and list2.
2. Point curr.next to the smaller node.
3. Advance the pointer of the list from which we took the node.
4. Advance the curr pointer.

Once we reach the end of either list, the while loop terminates. At this point, one list might still have remaining nodes. Because both input lists are sorted, any remaining nodes are guaranteed to be larger than the nodes already in our merged list. We can simply append the entire remainder of the non-empty list to curr.next.

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

def merge_two_sorted_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    # Initialize a dummy node to build the new list easily
    dummy = ListNode(-1)
    curr = dummy
    
    # Traverse both lists as long as neither is exhausted
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
            
        # Move the current pointer of the merged list forward
        curr = curr.next
        
    # At least one list is now exhausted. 
    # Attach the remaining elements of the other list.
    if list1:
        curr.next = list1
    elif list2:
        curr.next = list2
        
    # The merged list starts at dummy.next
    return dummy.next

• Time complexity: O(N + M) — In the worst-case scenario, we iterate through both lists completely. Since we only perform constant-time pointer assignments at each step, the total time is directly proportional to the total number of nodes.
• Space complexity: O(1) — We achieve sorting purely by rewiring existing node pointers. The only extra space consumed is for our dummy node and tracking pointers (curr, list1, list2), meaning no auxiliary memory proportional to the input size is used.

Edge Cases Handled

• Both lists are empty: (list1 = [], list2 = []). The while loop never executes. Both if/elif conditions at the end evaluate to false. The function correctly returns dummy.next, which is None.
• One list is empty: (list1 = [], list2 = [0]). The while loop skips, and the elif branch attaches list2 directly to the dummy node. The function immediately returns the non-empty list.
• Different lengths: The algorithm naturally handles disparate lengths because the termination condition of the while loop protects against NoneType errors, and the remainder block catches all leftover elements cleanly.

Tools Pro

Gemini is AI and can make mistakes.