A complete visual walkthrough of the iterative merge approach — from brute force to optimal, with linked list animations.
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 } }
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 } } }
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: O(1) for iterative. We reuse the existing nodes by rewiring their next pointers — no new nodes are allocated. The only extra memory is the dummy node and the curr pointer, both constant. The recursive version uses O(n+m) space due to the call stack.