Merge Two Sorted Lists
Problem
Given the heads of two sorted singly linked lists list1 and list2, merge the two lists into one sorted list and return the head of the merged list.
- 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
list1 = [1,2,4], list2 = [1,3,4][1,1,2,3,4,4]The algorithm starts with two pointers at the heads of list1 and list2. It compares the current nodes: both have value 1. It chooses the node from list1 first, linking it to the merged list. Then it advances list1's pointer. Next, it compares 2 (list1) and 1 (list2), chooses 1 from list2, and advances list2. This process continues, always linking the smaller current node to the merged list and advancing that pointer. When one list is exhausted, the remaining nodes of the other list are appended directly. The final merged list is sorted and contains all nodes from both lists.
Approach
Straightforward Solution
A naive approach might create a new list and copy values from both lists, but this wastes space and time. Another naive approach is to concatenate and then sort, which is inefficient (O(n log n)).
Core Observation
Merging two sorted lists is fundamentally about repeatedly choosing the smaller current node from either list and linking it to the merged list, preserving sorted order.
Path to Optimal
The key insight is to use two pointers to traverse both lists simultaneously, always linking the smaller node to the merged list and advancing that pointer. This approach exploits the sorted property to merge in a single pass with O(n) time and O(1) auxiliary space.
Optimal Approach
Initialize a dummy node to act as the start of the merged list and a tail pointer to track the last node in the merged list. While both lists have nodes, compare their current values, link the smaller node to tail.next, and advance the corresponding pointer and tail. After the loop, link the remaining nodes from the non-empty list to tail.next. Return dummy.next as the head of the merged list.
Time
O(n + m)
Each node from both lists is visited exactly once and linked into the merged list, resulting in linear time proportional to the total number of nodes.
Space
O(1)
The algorithm uses only a few pointers and does not allocate new nodes or data structures proportional to input size, achieving constant auxiliary space.
Pattern Spotlight
Linked List (Two-Pointer Merge)
When merging two sorted linked lists, use two pointers to traverse both lists simultaneously, always linking the smaller current node to the merged list and advancing that pointer, which guarantees a single linear pass with O(1) auxiliary space.
Solution
| 1 | class Solution:
|
| 2 | def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
|
| 3 | dummy = ListNode()
|
| 4 | tail = dummy
|
| 5 |
|
| 6 | while list1 and list2:
|
| 7 | if list1.val < list2.val:
|
| 8 | tail.next = list1
|
| 9 | list1 = list1.next
|
| 10 | else:
|
| 11 | tail.next = list2
|
| 12 | list2 = list2.next
|
| 13 | tail = tail.next
|
| 14 |
|
| 15 | if list1:
|
| 16 | tail.next = list1
|
| 17 | elif list2:
|
| 18 | tail.next = list2
|
| 19 |
|
| 20 | return dummy.next |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public ListNode mergeTwoLists(ListNode list1, ListNode list2) { |
| 5 | ListNode dummy = new ListNode(); |
| 6 | ListNode tail = dummy; |
| 7 | |
| 8 | while (list1 != null && list2 != null) { |
| 9 | if (list1.val < list2.val) { |
| 10 | tail.next = list1; |
| 11 | list1 = list1.next; |
| 12 | } else { |
| 13 | tail.next = list2; |
| 14 | list2 = list2.next; |
| 15 | } |
| 16 | tail = tail.next; |
| 17 | } |
| 18 | |
| 19 | if (list1 != null) { |
| 20 | tail.next = list1; |
| 21 | } else if (list2 != null) { |
| 22 | tail.next = list2; |
| 23 | } |
| 24 | |
| 25 | return dummy.next; |
| 26 | } |
| 27 | } |
| 1 | #include <iostream> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { |
| 8 | ListNode dummy; |
| 9 | ListNode* tail = &dummy; |
| 10 | |
| 11 | while (list1 != nullptr && list2 != nullptr) { |
| 12 | if (list1->val < list2->val) { |
| 13 | tail->next = list1; |
| 14 | list1 = list1->next; |
| 15 | } else { |
| 16 | tail->next = list2; |
| 17 | list2 = list2->next; |
| 18 | } |
| 19 | tail = tail->next; |
| 20 | } |
| 21 | |
| 22 | if (list1 != nullptr) { |
| 23 | tail->next = list1; |
| 24 | } else if (list2 != nullptr) { |
| 25 | tail->next = list2; |
| 26 | } |
| 27 | |
| 28 | return dummy.next; |
| 29 | } |
| 30 | }; |
| 1 | var mergeTwoLists = function(list1, list2) { |
| 2 | let dummy = new ListNode(); |
| 3 | let tail = dummy; |
| 4 | |
| 5 | while (list1 !== null && list2 !== null) { |
| 6 | if (list1.val < list2.val) { |
| 7 | tail.next = list1; |
| 8 | list1 = list1.next; |
| 9 | } else { |
| 10 | tail.next = list2; |
| 11 | list2 = list2.next; |
| 12 | } |
| 13 | tail = tail.next; |
| 14 | } |
| 15 | |
| 16 | if (list1 !== null) { |
| 17 | tail.next = list1; |
| 18 | } else if (list2 !== null) { |
| 19 | tail.next = list2; |
| 20 | } |
| 21 | |
| 22 | return dummy.next; |
| 23 | }; |
Step-by-Step Solution
Initialize Dummy Node and Tail Pointer to Build Merged List
| 3 | dummy = ListNode()
|
| 4 | tail = dummy
|
Objective
To create a starting point for the merged list and maintain a pointer to its last node for efficient appending.
Key Insight
Using a dummy node simplifies edge cases by providing a fixed starting node, avoiding special handling for the head of the merged list. The tail pointer always points to the last node in the merged list, enabling O(1) appends as nodes are linked.
Interview Quick-Check
Core Logic
The dummy node acts as a sentinel to simplify list construction, and the tail pointer tracks the end of the merged list for efficient linking.
Common Pitfalls & Bugs
Forgetting to initialize the tail pointer to the dummy node can cause incorrect linking or loss of the merged list head.
Iteratively Compare Nodes and Link the Smaller to the Merged List
| 6 | while list1 and list2:
|
| 7 | if list1.val < list2.val:
|
| 8 | tail.next = list1
|
| 9 | list1 = list1.next
|
| 10 | else:
|
| 11 | tail.next = list2
|
| 12 | list2 = list2.next
|
| 13 | tail = tail.next
|
Objective
To traverse both lists simultaneously, always appending the smaller current node to the merged list and advancing pointers accordingly.
Key Insight
Because both lists are sorted, the smallest node at each step must come from one of the two current nodes. By comparing and linking the smaller node, the merged list remains sorted. Advancing the pointer of the chosen node ensures progress and prevents infinite loops.
Interview Quick-Check
Core Logic
At each iteration, compare the current nodes of both lists, link the smaller node to the merged list, and advance that list's pointer and the tail pointer.
State & Boundaries
The loop continues while both lists have nodes, ensuring all nodes are processed.
Common Pitfalls & Bugs
Failing to advance the tail pointer after linking a node breaks the chain and corrupts the merged list.
Append Remaining Nodes from Non-Exhausted List to Complete Merge
| 15 | if list1:
|
| 16 | tail.next = list1
|
| 17 | elif list2:
|
| 18 | tail.next = list2
|
Objective
To link any leftover nodes from either list after the other is fully traversed, completing the merged list.
Key Insight
Since the input lists are sorted, the remaining nodes in the non-empty list are already in order and greater than all previously merged nodes. Directly linking them avoids unnecessary comparisons and preserves sorted order.
Interview Quick-Check
Core Logic
After one list is exhausted, append the remaining nodes of the other list directly to the merged list.
Common Pitfalls & Bugs
Neglecting to append the remaining nodes results in an incomplete merged list missing tail elements.
Return the Head of the Merged List Skipping Dummy Node
| 20 | return dummy.next |
Objective
To return the merged list starting from the first real node, excluding the dummy node.
Key Insight
The dummy node is a placeholder and not part of the actual merged list. Returning dummy.next provides the correct head of the merged list constructed during the process.
Interview Quick-Check
Core Logic
Return dummy.next to provide the head of the merged list, excluding the dummy sentinel node.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
tail.next = list1Link the smaller node (from list1) to the merged list.
Linking the smaller node preserves the sorted order and builds the merged list incrementally.
tail.next = list2Link the smaller node (from list2) to the merged list.
Linking the smaller node from list2 maintains the sorted order and continues building the merged list.
tail = tail.nextAdvance the tail pointer to the newly linked node.
Moving the tail pointer keeps it at the end of the merged list, enabling O(1) appends in subsequent iterations.
return dummy.nextReturn the head of the merged list, skipping the dummy node.
Returning dummy.next provides the actual start of the merged list, excluding the placeholder dummy node.
dummy = ListNode()Create a dummy node to serve as the fixed starting point of the merged list.
The dummy node simplifies edge cases by providing a non-null starting node, allowing uniform linking logic without special handling for the head.
list1 = list1.nextAdvance the pointer in list1 after linking its node.
Advancing the pointer moves forward in list1, ensuring progress and preventing infinite loops.
list2 = list2.nextAdvance the pointer in list2 after linking its node.
Advancing the pointer in list2 ensures progress and prevents infinite loops.
if list1:If list1 still has nodes, link the remaining nodes to the merged list.
Appending the remaining nodes from list1 preserves sorted order and completes the merged list.
elif list2:If list2 still has nodes, link the remaining nodes to the merged list.
Appending the remaining nodes from list2 preserves sorted order and completes the merged list.
tail = dummyInitialize the tail pointer to the dummy node to track the end of the merged list.
The tail pointer enables efficient appending of nodes by always pointing to the last node in the merged list, avoiding traversal.
if list1.val < list2.val:Compare the current values of list1 and list2 nodes.
The comparison determines which node should be linked next to maintain sorted order in the merged list.
else:Handle the case where list2's current node is smaller or equal.
This else branch ensures the smaller or equal node from list2 is linked, maintaining sorted order.
tail.next = list1Link the remaining nodes of list1 to tail.next.
Directly linking the leftover nodes avoids unnecessary comparisons and maintains correctness.
tail.next = list2Link the remaining nodes of list2 to tail.next.
Directly linking the leftover nodes avoids unnecessary comparisons and maintains correctness.
while list1 and list2:Start a loop that continues while both list1 and list2 have nodes.
This loop ensures that nodes are merged until at least one list is fully traversed, maintaining progress and correctness.
Test Your Understanding
Why is it safe to link the remaining nodes of one list directly after the other list is exhausted?
Because both input lists are sorted, the remaining nodes in the non-exhausted list are already greater than all nodes linked so far, so appending them preserves the sorted order of the merged list.
Related Problems
Linked Lists pattern
Don't just read it. Drill it.
Reconstruct Merge Two Sorted Lists from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Merge Two Sorted Lists drill