Problem Statement
Merge Two Sorted Lists
You are given the heads of two sorted linked lists, list1 and list2. A linked list is a chain of nodes, where each node holds a value and a pointer to the next node. Both chains are already sorted, meaning their values go from small to large as you walk along. Your job is to weave them together into one chain that is also sorted from small to large. You do not build new nodes, you reuse the ones you already have by re-linking their pointers. Return the head of the merged list, which is the first node of the new chain.
Translate the prompt
Merge two sorted linked lists into one sorted linked list, reusing the existing nodes (no new allocation beyond a dummy head).
Signals to notice
Brute force first
Dump all values into an array, sort, build a new list. O((m+n) log(m+n)) time and O(m+n) extra — ignores the sorted inputs.
The key insight
Because both inputs are sorted, the next node of the merged list is always the smaller of the two current heads. You never have to look further ahead than one node on each side.
Trace it on l1=1→3→5, l2=2→4
tail→dummy l1=1, l2=2 → 1 < 2 → tail.next=l1, tail=l1, l1=3 l1=3, l2=2 → 2 < 3 → tail.next=l2, tail=l2, l2=4 l1=3, l2=4 → 3 < 4 → tail.next=l1, tail=l1, l1=5 l1=5, l2=4 → 4 < 5 → tail.next=l2, tail=l2, l2=null l1 non-empty → tail.next=l1 (=5) return dummy.next: 1→2→3→4→5
What must stay true
The nodes reachable from `dummy.next` are a sorted prefix of the final answer, and the remaining nodes in l1 and l2 are all ≥ `tail.val`.
Shape of the loop
dummy = Node(0); tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next = l1; l1 = l1.next else: tail.next = l2; l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 return dummy.next
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Forgetting the final append of the non-empty list. Without it, the merged output truncates at the first exhausted input and drops all trailing elements of the other list.