Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
A complete visual walkthrough of the iterative merge approach — from brute force to optimal, with linked list animations.
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = [] Output: []
Example 3:
Input: list1 = [], list2 = [0] Output: [0]
Constraints:
[0, 50].-100 <= Node.val <= 100list1 and list2 are sorted in non-decreasing order.The simplest idea: collect all node values into an array, sort it, then build a new linked list from the sorted array.
This runs in O((n+m) log(n+m)) time because of the sort. But both lists are already sorted — we're throwing away that information and doing unnecessary work.
The wasted information: Both lists are already in order. If we just compare the heads of each list, we always know which element comes next — no sorting required. This is exactly the merge step of merge sort.
Since both lists are sorted, we can build the result in one pass. Use a dummy head node and a current pointer. At each step, compare the heads of both lists and attach the smaller one to the result.
Think of two queues of people sorted by height. To merge them into one sorted line, you repeatedly compare the person at the front of each queue and move the shorter one into the result line.
When one list is exhausted, just attach the remainder of the other list — it's already sorted!
Why a dummy head? Without it, we'd need special-case logic to initialize the head of the result list. The dummy node lets us always do curr.next = chosen without checking if the result is empty. We return dummy.next at the end to skip it.
Let's trace through the merge of list1 = [1,2,4] and list2 = [1,3,4] step by step.
list1 is exhausted (null). Attach all remaining nodes of list2.
The algorithm handles these naturally due to the dummy head and the final remainder attachment.
list1 = null, list2 = null → The while loop never executes. curr.next remains null. We return dummy.next which is null.list1 = [1,2,3], list2 = null → The while loop never executes. The final line curr.next = list1 attaches the entire non-empty list.list1 = [1], list2 = [2,5,8,10] → After one comparison picks 1 from list1, list1 becomes null. The remainder of list2 is attached directly.list1 = [1,2,3], list2 = [7,8,9] → All three comparisons pick from list1. Then list1 exhausts and the entire list2 is appended. Result: [1,2,3,7,8,9].No special cases needed. The dummy head pattern and the single line curr.next = (list1 != null) ? list1 : list2 handle every edge case without any if branching for empty inputs. This is why the dummy head technique is so valuable.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { this.val = val; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // Dummy head avoids special-case logic for empty result ListNode dummy = new ListNode(0); ListNode curr = dummy; // tail of result list // Compare heads while both lists have nodes while (list1 != null && list2 != null) { if (list1.val <= list2.val) { curr.next = list1; // attach list1's head list1 = list1.next; // advance list1 } else { curr.next = list2; // attach list2's head list2 = list2.next; // advance list2 } curr = curr.next; // advance result tail } // Attach whichever list still has remaining nodes curr.next = (list1 != null) ? list1 : list2; return dummy.next; // skip dummy, return real head } }
// Definition for singly-linked list. // type ListNode struct { // Val int // Next *ListNode // } func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { // Dummy head avoids special-case logic for empty result dummy := &ListNode{} curr := dummy // tail of result list // Compare heads while both lists have nodes for list1 != nil && list2 != nil { if list1.Val <= list2.Val { curr.Next = list1 // attach list1's head list1 = list1.Next // advance list1 } else { curr.Next = list2 // attach list2's head list2 = list2.Next // advance list2 } curr = curr.Next // advance result tail } // Attach whichever list still has remaining nodes if list1 != nil { curr.Next = list1 } else { curr.Next = list2 } return dummy.Next // skip dummy, return real head }
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def merge_two_lists( self, list1: Optional[ListNode], list2: Optional[ListNode] ) -> Optional[ListNode]: # Dummy head avoids special-case logic for empty result dummy = ListNode(0) curr = dummy # tail of result list # Compare heads while both lists have nodes while list1 and list2: if list1.val <= list2.val: curr.next = list1 # attach list1's head list1 = list1.next # advance list1 else: curr.next = list2 # attach list2's head list2 = list2.next # advance list2 curr = curr.next # advance result tail # Attach whichever list still has remaining nodes curr.next = list1 if list1 else list2 return dummy.next # skip dummy, return real head
// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { pub val: i32, pub next: Option<Box<ListNode>> } impl Solution { pub fn merge_two_lists( list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { match (list1, list2) { // Base cases: one list exhausted, return the other (None, l2) => l2, (l1, None) => l1, // Both lists have nodes — pick the smaller head (Some(mut l1), Some(mut l2)) => { if l1.val <= l2.val { l1.next = Solution::merge_two_lists(l1.next.take(), Some(l2)); Some(l1) // l1 becomes the head } else { l2.next = Solution::merge_two_lists(Some(l1), l2.next.take()); Some(l2) // l2 becomes the head } } } } }
// Definition for singly-linked list. class ListNode { val: number; next: ListNode | null; constructor(val: number = 0, next: ListNode | null = null) { this.val = val; this.next = next; } } function mergeTwoLists( list1: ListNode | null, list2: ListNode | null ): ListNode | null { // Dummy head avoids special-case logic for empty result const dummy = new ListNode(0); let curr = dummy; // tail of result list // Compare heads while both lists have nodes while (list1 !== null && list2 !== null) { if (list1.val <= list2.val) { curr.next = list1; // attach list1's head list1 = list1.next; // advance list1 } else { curr.next = list2; // attach list2's head list2 = list2.next; // advance list2 } curr = curr.next!; // advance result tail } // Attach whichever list still has remaining nodes curr.next = list1 ?? list2; return dummy.next; // skip dummy, return real head }
The recursive approach is elegant but uses O(n+m) stack space. For very long lists, this could cause a stack overflow. The iterative version above is preferred in interviews.
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; // base case: l1 exhausted if (l2 == null) return l1; // base case: l2 exhausted if (l1.val <= l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; // l1 becomes the head } else { l2.next = mergeTwoLists(l1, l2.next); return l2; // l2 becomes the head } } }
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } // base case: l1 exhausted if l2 == nil { return l1 } // base case: l2 exhausted if l1.Val <= l2.Val { l1.Next = mergeTwoLists(l1.Next, l2) return l1 // l1 becomes the head } l2.Next = mergeTwoLists(l1, l2.Next) return l2 // l2 becomes the head }
class Solution: def merge_two_lists( self, l1: Optional[ListNode], l2: Optional[ListNode] ) -> Optional[ListNode]: if not l1: return l2 # base case: l1 exhausted if not l2: return l1 # base case: l2 exhausted if l1.val <= l2.val: l1.next = self.merge_two_lists(l1.next, l2) return l1 # l1 becomes the head else: l2.next = self.merge_two_lists(l1, l2.next) return l2 # l2 becomes the head
impl Solution { pub fn merge_two_lists( l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>, ) -> Option<Box<ListNode>> { match (l1, l2) { (None, l2) => l2, // base case: l1 exhausted (l1, None) => l1, // base case: l2 exhausted (Some(mut n1), Some(mut n2)) => { if n1.val <= n2.val { n1.next = Solution::merge_two_lists(n1.next.take(), Some(n2)); Some(n1) // n1 becomes the head } else { n2.next = Solution::merge_two_lists(Some(n1), n2.next.take()); Some(n2) // n2 becomes the head } } } } }
function mergeTwoLists( l1: ListNode | null, l2: ListNode | null ): ListNode | null { if (l1 === null) return l2; // base case: l1 exhausted if (l2 === null) return l1; // base case: l2 exhausted if (l1.val <= l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; // l1 becomes the head } else { l2.next = mergeTwoLists(l1, l2.next); return l2; // l2 becomes the head } }
Enter two sorted lists and step through the merge. Watch nodes move from the input lists into the result.
Each node is visited exactly once. The while loop runs at most n + m iterations (where n and m are the lengths of the two lists), and each iteration does O(1) work: one comparison and one pointer reassignment. Space is O(1) for the iterative approach — we reuse existing nodes by rewiring their next pointers.
Collect all node values from both lists into an array of size n+m, then sort it. The sort dominates at O((n+m) log(n+m)). Building the output list from the sorted array requires O(n+m) additional space for the array and new nodes.
A single while loop compares the heads of both lists, picking the smaller node each iteration. Each node is visited exactly once, giving O(n+m) time. Existing nodes are rewired in place with only a dummy head and a tail pointer, so auxiliary space is O(1).
Each recursive call processes one node by picking the smaller head and recursing on the rest. There are n+m calls total, each doing O(1) work. However, the call stack grows to depth n+m in the worst case, using O(n+m) space for stack frames.
The dummy head node eliminates all edge cases. Without it, you need special logic to initialize the result's first node. With it, curr.next = chosen always works, even when the result is empty. Merging is inherently linear — you must inspect every node at least once — so O(n + m) is optimal.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.