Merge Two Sorted Lists
Merging two sorted linked lists produces a single sorted linked list containing all nodes from both input lists. This operation is the core subroutine in m...
Combining Two Ordered Linked Lists into One Sorted Result
Merging two sorted linked lists produces a single sorted linked list containing all nodes from both input lists. This operation is the core subroutine in merge sort on linked lists and tests your ability to manage multiple pointers across two independent chains.
The iterative approach uses a dummy head node to simplify the edge case where the result list starts with nodes from either input list. Create a dummy node and a current pointer initially pointing to it. Then use a while loop that continues as long as both list1 and list2 are non-null. At each step, compare list1.data with list2.data. Append the smaller node to current.next, advance the corresponding list pointer to its next node, and advance current to current.next. When one list is exhausted, append the remainder of the other by setting current.next to whichever list is non-null.
The dummy head trick works because it eliminates the need to handle the first node specially. Without it, you would need to determine which list provides the head of the result before entering the loop, adding conditional logic. With dummy, the first iteration simply adds the smaller of the two initial nodes to dummy.next.
The total number of steps is proportional to the sum of the lengths of both lists, giving O(n plus m) time where n and m are the respective lengths. Space is O(1) because you reuse the existing nodes; no new nodes are created (only the dummy node, which is O(1)).
The recursive approach is more concise. Base cases: if list1 is null, return list2; if list2 is null, return list1. Recursive case: compare list1.data with list2.data. If list1 is smaller or equal, set list1.next to merge(list1.next, list2) and return list1. Otherwise, set list2.next to merge(list1, list2.next) and return list2. The recursion depth is O(n plus m), consuming O(n plus m) stack space, making the iterative approach preferable for very long lists.
Merging k sorted lists generalizes this problem. A naive approach merges them pairwise, taking O(n times k) time. Using a min-heap that holds one node from each list at a time gives O(n log k) time, where n is the total number of nodes.
Worked example: merge [1, 3, 5] and [2, 4, 6]. Iterative trace: compare 1 and 2, append 1. Compare 3 and 2, append 2. Compare 3 and 4, append 3. Compare 5 and 4, append 4. Compare 5 and 6, append 5. List1 exhausted, append remainder [6]. Result: [1, 2, 3, 4, 5, 6].
Interview tip: implement the iterative version first (it is O(1) space), then offer the recursive version as a cleaner alternative. Mention that for very long lists, the iterative version avoids stack overflow risk.