Merging Linked Lists

1. Introduction: Zipper Logic

Imagine a jacket zipper. You have two sides of interlocking teeth. As you pull the slider up, it takes one tooth from the left, one from the right, perfectly interlocking them into a single, unified chain.

In computer science, Merging Linked Lists is the process of taking two separate lists (usually already sorted) and weaving them together into a single sorted list. Unlike merging arrays—which requires allocating a completely new array in memory and copying values over—merging Linked Lists is a purely structural operation. You don't create new nodes; you just reorganize the existing next pointers. This makes it an incredibly fast $O(1)$ space operation.

2. Core Concept: The Dummy Node Pattern

The most difficult part of merging lists is handling the very first node. Which list contributes the first node? What if one list is empty? If we try to track the head of our new merged list dynamically, we end up writing messy if/else logic to initialize it.

The Solution: The Dummy Node We create a fake node (e.g., ListNode dummy = new ListNode(0)). We anchor a tail pointer to it. As we iterate through our two lists, we append the winning nodes to tail.next. When the algorithm finishes, the true start of our merged list is simply dummy.next! The dummy node completely shields us from null initialization edge cases.

3. Beginner Code Example: Merge Two Sorted Lists

Problem Statement: (LeetCode 21) 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.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeTwoLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 1. Initialize Dummy Node and Tail
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        
        // 2. Zipper Loop
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1; // Link to l1
                l1 = l1.next;   // Move l1 forward
            } else {
                tail.next = l2; // Link to l2
                l2 = l2.next;   // Move l2 forward
            }
            tail = tail.next;   // Move tail forward
        }
        
        // 3. Attach remaining nodes
        // If one list finishes early, the other list is already sorted!
        // We just attach the rest of it in one O(1) pointer assignment.
        if (l1 != null) {
            tail.next = l1;
        } else if (l2 != null) {
            tail.next = l2;
        }
        
        // 4. Return the true head
        return dummy.next;
    }
}

Complexity Analysis:

• Time Complexity: $O(N + M)$ where $N$ and $M$ are the lengths of the two lists. We process each node exactly once.
• Space Complexity: $O(1)$. We are only rearranging existing pointers, not creating new nodes.

4. Intermediate Code Example: Sort List (Merge Sort)

Problem Statement: (LeetCode 148) Given the head of a linked list, return the list after sorting it in ascending order. You must do this in $O(N \log N)$ time and $O(1)$ space.

The Insight: Arrays use Quick Sort, but Linked Lists heavily favor Merge Sort. Why? Because finding the middle of a list takes $O(N)$ using Fast/Slow pointers, and merging two lists takes $O(N)$ with $O(1)$ space! It is perfectly tailored for Linked Lists.

public class SortLinkedList {
    public ListNode sortList(ListNode head) {
        // Base case: 0 or 1 node is already sorted
        if (head == null || head.next == null) return head;
        
        // 1. Find the middle of the list
        ListNode mid = getMid(head);
        ListNode rightHead = mid.next;
        
        // CRITICAL: Sever the connection to split the list into two distinct halves!
        mid.next = null;
        
        // 2. Recursively sort the left half and right half
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        
        // 3. Merge the sorted halves
        return MergeTwoLists.mergeTwoLists(left, right); // Using our function from above!
    }
    
    // Helper function using Fast/Slow pointers
    private ListNode getMid(ListNode head) {
        ListNode slow = head;
        // Fast starts one step ahead so slow ends up on the FIRST middle node for even lengths
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

(Note: Recursive Merge Sort technically uses $O(\log N)$ space on the call stack. A true $O(1)$ space solution requires a highly complex Iterative Bottom-Up Merge Sort, but interviewers universally accept the Recursive version).

5. Advanced Code Example: Merge K Sorted Lists

Problem Statement: (LeetCode 23) You are given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list.

(Note: We covered the Min-Heap solution in the Heap chapter, which is highly recommended. However, we can also solve this purely using the Divide & Conquer Merge logic).

Divide & Conquer Approach: Instead of merging list 1 into list 2, then list 3 into the result, then list 4 into the result (which takes $O(K \times N)$ time), we pair them up! Merge 1 & 2. Merge 3 & 4. Then merge (1+2) with (3+4). This halves the number of lists in every pass, reducing the time to $O(N \log K)$.

public class MergeKListsDC {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        
        int interval = 1;
        int n = lists.length;
        
        // Pair up lists and merge them, doubling the interval every pass
        while (interval < n) {
            for (int i = 0; i < n - interval; i += interval * 2) {
                lists[i] = MergeTwoLists.mergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        
        return lists[0];
    }
}

6. Common Mistakes Beginners Make

1. Forgetting to sever the list in Merge Sort

   • The Mistake: Finding the middle node, but forgetting to do mid.next = null.
   • Why it's wrong: If you don't sever the link, the "left half" still mathematically contains the "right half". When you pass the left half into the recursive call, it will infinitely recurse on the full length of the list, throwing a StackOverflowError.

2. Re-inventing the wheel for odd/even lengths

   • The Mistake: Writing massive if (length % 2 == 0) blocks.
   • The Fix: The Fast/Slow pointer mathematically handles odd and even lengths beautifully. If you initialize fast = head.next, the slow pointer will always land on the exact node where you should perform the split, regardless of length.

3. Returning dummy instead of dummy.next

   • The Mistake: Your function returns dummy.
   • Why it's wrong: The user will see a list that looks like -1 -> 2 -> 4 -> 5. The -1 is a fake node that shouldn't be part of the final data structure!

7. Interview Q&A

Q1: Why is Merge Sort preferred over Quick Sort for Linked Lists? Answer: Quick Sort requires randomly accessing elements to swap them with the pivot, or maintaining complex back-pointers. Since Linked Lists are sequential, finding elements is $O(N)$. Merge Sort only requires sequential access, making it naturally tailored for the Linked List structure. Furthermore, merging Linked Lists takes $O(1)$ space, removing the major space-penalty usually associated with Array Merge Sort.

Q2: How do you handle intersecting Linked Lists? (LeetCode 160) Answer: If two lists merge (like a Y shape), they share the same memory references from the intersection point onwards. You can find the intersection by resetting pointers: Traverse list A. When it hits null, start it at the head of list B. Traverse list B. When it hits null, start it at the head of list A. They are mathematically guaranteed to collide exactly at the intersection point!

Q3: Can you merge lists without a Dummy Node? Answer: Yes, but you must manually check if (l1.val <= l2.val) { head = l1; ... } else { head = l2; ... } and keep track of it before the loop starts. The Dummy Node pattern eliminates 10 lines of fragile initialization code.

8. Practice Problems

1. Merge Two Sorted Lists (LeetCode 21)
   • Goal: Write the Dummy Node pattern from memory perfectly.
2. Sort List (LeetCode 148)
   • Goal: Combine Fast/Slow pointers (to find mid) with Merge logic.
3. Merge In Between Linked Lists (LeetCode 1669)
   • Hint: Traverse to the split points, cut out the middle segment, and splice the new list directly in using pure pointer assignments.

9. Summary

• Dummy Node: The ultimate cheat code for Linked List problems. ListNode dummy = new ListNode(0); ListNode tail = dummy;.
• Zipper Logic: Compare l1.val and l2.val. Point tail.next to the winner. Advance the winner and the tail.
• The Leftovers: When the while(l1 != null && l2 != null) loop breaks, one list still has nodes. Attach them instantly with tail.next = l1 != null ? l1 : l2;.
• Merge Sort: The absolute best sorting algorithm for Linked Lists, leveraging Fast/Slow pointers to split the list.