Merge Two Sorted Linked Lists — Iterative, Recursive & In-Place
Merging two sorted linked lists is one of those problems that shows up everywhere once you know what to look for. It's the backbone of Merge Sort on linked lists, it powers external sorting in databases when data comes in pre-sorted chunks, and it's a core primitive in priority-queue implementations. If you've ever wondered how your music app merges two playlists that are already sorted alphabetically without re-sorting the whole thing, this is the algorithm doing that job.
The problem it solves is deceptively simple: given two linked lists where each is individually sorted in ascending order, produce a single sorted linked list containing all the nodes from both. The naive approach — dump everything into an array, sort it, rebuild a list — throws away the sorted order you already have and runs in O(n log n). The smart approach exploits that existing order to do it in O(n + m) time, where n and m are the lengths of the two lists, and O(1) extra space if done in-place.
By the end of this article you'll be able to implement both the iterative and recursive solutions from scratch, explain the trade-offs between them, wire up a real working Java program to verify both approaches produce identical results, and walk into any technical interview knowing exactly which version to reach for and why. Let's build it step by step.
Understanding the Structure Before Writing a Single Line of Code
Before touching any merge logic, you need a crystal-clear picture of what a linked list node actually holds. Each node is a small container with two things: a value (the data you care about) and a pointer to the next node. That 'next' pointer is what chains nodes together into a sequence — there's no array index, no random access, just 'follow the arrow to the next node'.
When we say two lists are 'sorted', we mean each list's internal order is correct. List A might hold [1 → 3 → 5 → 9] and List B might hold [2 → 4 → 6 → 8]. Neither list knows the other exists. Your job is to produce [1 → 2 → 3 → 4 → 5 → 6 → 8 → 9] by re-wiring the 'next' pointers — not by copying values.
This re-wiring of pointers is the key insight. You're not creating new nodes. You're changing where existing nodes point. That's what makes this O(1) extra space — you're just redirecting arrows, not allocating memory. Think of the theme park attendant: they don't clone people, they just point at who steps forward next.
One more thing to nail down before coding: you'll need a 'dummy' head node. This is a sentinel node you create at the start with a throwaway value. It gives your pointer-manipulation code a stable starting point so you never have to special-case 'what if the result list is empty so far'. You throw the dummy away at the end and return dummy.next.
// This is the fundamental building block for both approaches. // Keep it simple — one value, one pointer. public class ListNode { int value; // The actual data this node holds ListNode next; // Arrow pointing to the next node (null if this is the last node) // Constructor for quickly creating a node with a value ListNode(int value) { this.value = value; this.next = null; // By default, a new node points to nothing } // ── Helper: build a linked list from a plain int array ────────────────── // This lets us write clean test setups without constructing nodes manually. public static ListNode fromArray(int[] values) { if (values == null || values.length == 0) return null; ListNode head = new ListNode(values[0]); // First node becomes the head ListNode current = head; // Pointer we'll advance for (int i = 1; i < values.length; i++) { current.next = new ListNode(values[i]); // Attach new node to the chain current = current.next; // Move our pointer forward } return head; } // ── Helper: print the list so we can verify output ─────────────────────── public static String toString(ListNode head) { StringBuilder result = new StringBuilder(); ListNode current = head; while (current != null) { result.append(current.value); if (current.next != null) result.append(" → "); current = current.next; } return result.toString(); } }
The Iterative Solution — How the Ride Attendant Actually Works
The iterative approach mirrors what a human would do physically. You stand at the front of both lines, look at the two people at the front, and always tap the shorter one to step forward into the merged line. When one line empties, you wave the entire remaining line through without checking anyone — they're already in order.
In code, you maintain two pointers — call them pointerA and pointerB — positioned at the current heads of each list. At every step you compare their values. The smaller one gets attached to your result list, and that pointer advances one step. The other pointer stays put. Repeat until one list is exhausted, then attach the non-null list's remaining nodes in one shot.
The crucial implementation detail is the 'tail' pointer. You need to track the last node of your result list so you can attach the next winning node in O(1). If you walked from the head each time to find the end, you'd blow your time complexity to O(n²). Keep a tail pointer and always update it after each attachment.
This runs in O(n + m) time — you visit each node exactly once. Space is O(1) because you only allocate the dummy head node, and that's a constant regardless of input size. This is the version to reach for in production code: predictable performance, no call stack risk, easy to step through with a debugger.
public class MergeSortedListsIterative { public static ListNode mergeSortedLists(ListNode headA, ListNode headB) { // Dummy node gives us a stable starting point so we never have to // special-case 'what if the result list has no nodes yet'. ListNode dummy = new ListNode(-1); ListNode tail = dummy; // 'tail' always points to the last node in our result ListNode pointerA = headA; // Our cursor walking through List A ListNode pointerB = headB; // Our cursor walking through List B // Keep going as long as BOTH lists have unprocessed nodes while (pointerA != null && pointerB != null) { if (pointerA.value <= pointerB.value) { // List A's front node is smaller (or equal) — attach it to result tail.next = pointerA; // Wire the winning node onto our result chain pointerA = pointerA.next; // Advance List A's cursor one step forward } else { // List B's front node is smaller — attach it to result tail.next = pointerB; // Wire List B's node onto our result chain pointerB = pointerB.next; // Advance List B's cursor one step forward } tail = tail.next; // Move our result chain's tail to the newly attached node } // At this point one list is exhausted. The other may still have nodes. // Since both remaining sub-lists are already sorted, we can attach in bulk. if (pointerA != null) { tail.next = pointerA; // Attach all remaining nodes from List A at once } else { tail.next = pointerB; // Attach all remaining nodes from List B at once } // dummy.next is the true head of our merged list — skip the sentinel return dummy.next; } public static void main(String[] args) { // Build List A: 1 → 3 → 5 → 9 ListNode listA = ListNode.fromArray(new int[]{1, 3, 5, 9}); // Build List B: 2 → 4 → 6 → 8 ListNode listB = ListNode.fromArray(new int[]{2, 4, 6, 8}); System.out.println("List A: " + ListNode.toString(listA)); System.out.println("List B: " + ListNode.toString(listB)); ListNode merged = mergeSortedLists(listA, listB); System.out.println("Merged: " + ListNode.toString(merged)); // Edge case: one list is empty ListNode emptyList = null; ListNode singleItem = ListNode.fromArray(new int[]{42}); ListNode mergedEdge = mergeSortedLists(emptyList, singleItem); System.out.println("\nEdge case (null + single node): " + ListNode.toString(mergedEdge)); // Edge case: lists with duplicate values ListNode listC = ListNode.fromArray(new int[]{1, 4, 4, 7}); ListNode listD = ListNode.fromArray(new int[]{2, 4, 5}); ListNode mergedDupes = mergeSortedLists(listC, listD); System.out.println("Duplicates merged: " + ListNode.toString(mergedDupes)); } }
List B: 2 → 4 → 6 → 8
Merged: 1 → 2 → 3 → 4 → 5 → 6 → 8 → 9
Edge case (null + single node): 42
Duplicates merged: 1 → 2 → 4 → 4 → 4 → 5 → 7
The Recursive Solution — Elegant, But Know Its Cost
The recursive approach reads almost like the problem statement itself, which is why interviewers love it as a follow-up. The logic is: 'the merged list starts with whichever head is smaller, and its tail is the result of recursively merging the rest'. It's a beautiful expression of the problem, and it's often what candidates reach for first.
Here's exactly what happens at each call: compare the two heads, pick the smaller one, set its 'next' to whatever the recursive call returns, then return that node. The base cases handle null inputs — if either list is exhausted, return the other list directly (since it's already sorted and fully valid).
However, the elegance comes with a real cost you must communicate in interviews: stack depth. Every recursive call consumes a stack frame. With two lists of combined length N, you make N recursive calls. Most JVMs have a default stack size that handles thousands of calls comfortably, but with very long lists (millions of nodes), you'll hit a StackOverflowError. The iterative version uses O(1) stack space. Recursive uses O(n + m) stack space.
This doesn't mean recursive is wrong — for interview demos, code clarity, or short lists, it's excellent. But in production with unbounded input, prefer iterative. Knowing both and being able to articulate this trade-off is what separates a strong candidate from an average one.
public class MergeSortedListsRecursive { public static ListNode mergeSortedLists(ListNode headA, ListNode headB) { // ── Base cases ───────────────────────────────────────────────────── // If List A is exhausted, the answer is just whatever remains in List B if (headA == null) return headB; // If List B is exhausted, the answer is just whatever remains in List A if (headB == null) return headA; // ── Recursive case ───────────────────────────────────────────────── if (headA.value <= headB.value) { // headA is the smaller node — it becomes the current head of our result. // Its 'next' should be the result of merging the REST of List A // with ALL of List B. We let recursion figure that out. headA.next = mergeSortedLists(headA.next, headB); return headA; // headA is now correctly linked — return it up the call stack } else { // headB is the smaller node — same logic, mirrored headB.next = mergeSortedLists(headA, headB.next); return headB; // headB is now correctly linked — return it up the call stack } // When every recursive call returns, each node's 'next' points to the // next smallest node across both lists. The result unwinds perfectly. } public static void main(String[] args) { // Same test cases as the iterative version — results must be identical ListNode listA = ListNode.fromArray(new int[]{1, 3, 5, 9}); ListNode listB = ListNode.fromArray(new int[]{2, 4, 6, 8}); System.out.println("List A: " + ListNode.toString(listA)); System.out.println("List B: " + ListNode.toString(listB)); ListNode merged = mergeSortedLists(listA, listB); System.out.println("Merged: " + ListNode.toString(merged)); // Demonstrate with one empty list — recursive base case fires immediately ListNode result = mergeSortedLists(null, ListNode.fromArray(new int[]{7, 14, 21})); System.out.println("\nOne empty list: " + ListNode.toString(result)); // Both lists empty — returns null, which represents an empty list ListNode bothEmpty = mergeSortedLists(null, null); System.out.println("Both empty: " + (bothEmpty == null ? "(empty list)" : ListNode.toString(bothEmpty))); } }
List B: 2 → 4 → 6 → 8
Merged: 1 → 2 → 3 → 4 → 5 → 6 → 8 → 9
One empty list: 7 → 14 → 21
Both empty: (empty list)
Where This Algorithm Actually Lives in the Real World
Merging two sorted linked lists isn't just a leetcode exercise — it's a primitive that underpins several important real-world systems. The most direct application is Merge Sort on linked lists. Unlike arrays, linked lists can't be split by index in O(1), but they're perfectly suited for merge sort because splitting at the midpoint just requires finding it once, and merging is in-place with no extra array allocation. Merge Sort on a linked list is actually O(1) space, which beats array-based merge sort.
Database systems use this pattern during external merge sort — when a dataset is too large for RAM, it's sorted in chunks and those pre-sorted chunks are merged together. Each chunk is effectively a sorted list, and the merge step is exactly this algorithm scaled up.
Another practical case: merging two ordered event logs. If you have audit logs from two servers, both timestamped in order, and you need a unified chronological view, this algorithm produces that in linear time without touching a sorting algorithm.
In Java specifically, the java.util.PriorityQueue and several stream merge operations under the hood use variations of this pattern. Understanding it deeply means you can reason about the performance of those standard library components when composing them in real systems.
The pattern also generalizes: once you know how to merge two sorted lists, merging K sorted lists (using a min-heap to pick the smallest head at each step) becomes a natural extension — and that's a problem that appears in distributed systems constantly.
// Real-world use: Merge Sort implemented on a linked list. // This shows WHY merging two sorted lists matters — it's the core step // of one of the most important sorting algorithms. public class MergeSortLinkedList { // ── Entry point: sort the entire linked list ───────────────────────────── public static ListNode mergeSort(ListNode head) { // Base case: a list of 0 or 1 nodes is already sorted if (head == null || head.next == null) return head; // Step 1: find the midpoint so we can split the list into two halves ListNode midpoint = findMidpoint(head); ListNode secondHalfHead = midpoint.next; midpoint.next = null; // Physically cut the list into two separate lists // Step 2: recursively sort each half ListNode sortedFirstHalf = mergeSort(head); ListNode sortedSecondHalf = mergeSort(secondHalfHead); // Step 3: merge the two sorted halves — THIS is the function we built! return MergeSortedListsIterative.mergeSortedLists(sortedFirstHalf, sortedSecondHalf); } // Finds the middle node using the fast/slow pointer technique. // slow advances 1 step, fast advances 2 steps — when fast hits the end, // slow is sitting at the midpoint. Classic tortoise-and-hare. private static ListNode findMidpoint(ListNode head) { ListNode slow = head; ListNode fast = head.next; // Start fast one step ahead to get the LEFT mid on even lists while (fast != null && fast.next != null) { slow = slow.next; // Move slow one step fast = fast.next.next; // Move fast two steps } return slow; // slow is now at the midpoint } public static void main(String[] args) { // An unsorted list — we'll sort it using merge sort built on our merge function ListNode unsortedList = ListNode.fromArray(new int[]{8, 3, 1, 6, 2, 9, 4, 7, 5}); System.out.println("Before sort: " + ListNode.toString(unsortedList)); ListNode sortedList = mergeSort(unsortedList); System.out.println("After sort: " + ListNode.toString(sortedList)); // Simulate merging two ordered event logs by timestamp ListNode serverOneLog = ListNode.fromArray(new int[]{101, 204, 307, 502}); ListNode serverTwoLog = ListNode.fromArray(new int[]{150, 255, 410, 490, 610}); System.out.println("\nServer 1 log: " + ListNode.toString(serverOneLog)); System.out.println("Server 2 log: " + ListNode.toString(serverTwoLog)); ListNode unifiedLog = MergeSortedListsIterative.mergeSortedLists(serverOneLog, serverTwoLog); System.out.println("Unified log: " + ListNode.toString(unifiedLog)); } }
After sort: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
Server 1 log: 101 → 204 → 307 → 502
Server 2 log: 150 → 255 → 410 → 490 → 610
Unified log: 101 → 150 → 204 → 255 → 307 → 410 → 490 → 502 → 610
| Feature / Aspect | Iterative Approach | Recursive Approach |
|---|---|---|
| Time Complexity | O(n + m) | O(n + m) |
| Space Complexity | O(1) — only the dummy node | O(n + m) — call stack frames |
| Stack Overflow Risk | None — no call stack growth | Yes — deep lists can overflow JVM stack |
| Code Readability | Moderate — explicit pointer management | High — reads like the problem definition |
| Debuggability | Easy — step through loop iterations | Harder — must trace recursive call stack |
| Best For | Production code, large or unbounded lists | Interviews, short lists, clarity demos |
| Handles null inputs | Yes — while loop simply never runs | Yes — base case returns immediately |
| Modifies input nodes | Yes — re-wires .next pointers | Yes — re-wires .next pointers |
| Extra node allocation | 1 dummy node only | 0 extra nodes |
🎯 Key Takeaways
- The dummy/sentinel head node eliminates all 'is the result list empty?' special cases — always use it when building a linked list from scratch inside a function.
- Iterative and recursive merge have identical O(n + m) time complexity, but recursive uses O(n + m) stack space versus O(1) for iterative — this distinction is what interviewers are actually testing when they ask for both.
- Merging two sorted linked lists is not just a standalone problem — it's the merge step of linked list Merge Sort, which uniquely achieves O(n log n) time with O(1) extra space, something array Merge Sort cannot do.
- When one list is exhausted, attach the entire remaining other list in one pointer assignment — never loop through the remainder node by node, since it's already sorted and that bulk attachment is O(1).
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Not handling the null/empty list edge cases — Symptom: NullPointerException when either input is null, because the code immediately dereferences headA.value or headB.value without checking — Fix: always check 'if (headA == null) return headB' and 'if (headB == null) return headA' as your very first lines, before any comparison logic.
- ✕Mistake 2: Forgetting to advance the 'tail' pointer in the iterative version — Symptom: the merged list contains only 2 nodes no matter how large the input is, because tail.next gets overwritten at every iteration instead of growing — Fix: after every 'tail.next = someNode' assignment, immediately follow it with 'tail = tail.next' to move the tail forward to the newly attached node.
- ✕Mistake 3: Not severing the losing node's old 'next' pointer when building iteratively — Symptom: cycles appear in the merged list causing infinite loops when printing, because the losing node still points to where it used to point in the original list — Fix: in most standard implementations the tail pointer overwrites those links naturally, but be especially careful when the two lists have interleaved values; always trace through a small example by hand to verify no back-pointers remain.
Interview Questions on This Topic
- QCan you implement merge of two sorted linked lists both iteratively and recursively, then tell me exactly why their space complexities differ even though their time complexities are the same?
- QWhat happens to your merge function if both lists contain duplicate values — does it still produce a correctly sorted result, and how would you modify it if the requirement was to eliminate duplicates during the merge?
- QYour merged list looks correct on small inputs but causes an infinite loop on large ones — what's the most likely cause, and how would you systematically debug it without a debugger available?
Frequently Asked Questions
Does merging two sorted linked lists create new nodes or modify existing ones?
It modifies existing nodes by re-wiring their 'next' pointers — no new data nodes are created. The only new node in the iterative version is the dummy sentinel head, which is discarded before returning. This is what makes the algorithm O(1) extra space.
What if the two linked lists are sorted in descending order instead of ascending?
Flip the comparison operator. Change 'headA.value <= headB.value' to 'headA.value >= headB.value'. Everything else — the pointer logic, the base cases, the bulk tail attachment — stays identical. The algorithm is direction-agnostic as long as both lists are sorted in the same direction.
Why do we use a dummy head node instead of just tracking the result head separately?
Without a dummy node, you'd need an if-statement before the loop to set the result head to whichever list wins the first comparison — that's a special case that clutters the code. The dummy node means every node, including the very first real one, is attached via 'tail.next = node', making the loop body uniform with zero special cases. It's a small trick with a big clarity payoff.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.