Introduction & Problem Explanation

The Merge Two Sorted Lists problem asks us to merge two sorted singly linked lists into a single sorted linked list. The new list should be made by splicing together the nodes of the first two lists, keeping the elements in ascending order.

For example, if list1 = 1 -> 2 -> 4 and list2 = 1 -> 3 -> 4, the merged list should be 1 -> 1 -> 2 -> 3 -> 4 -> 4. The key constraint is that we should do this in-place by updating the existing next pointer references of the nodes rather than creating new node instances, which is highly efficient.

Illustration of merging two sorted linked lists iteratively in Java
Real-World Analogy: Merging Two Sorted Card Piles

Imagine you have two separate piles of playing cards lying face up on the table. Both piles are already sorted in ascending order (e.g., Pile A is [1, 3, 5] and Pile B is [2, 4, 6]). To merge them into a single sorted pile, you compare the top card of Pile A with the top card of Pile B. You pick the smaller card, place it face down at the end of your new combined pile, and move to the next card in that pile. You repeat this comparison step until one of the piles is completely empty. When that happens, you simply take the remaining cards from the non-empty pile and place them at the end of your new pile all at once!

The Algorithmic Approach

1. Iterative Merge (O(n + m) Time, O(1) Space)

We use a dummy helper node to anchor the start of our new merged list. We also maintain a pointer curr that starts at this dummy node.

  • We compare the values of the current nodes of list1 and list2.
  • We link the node with the smaller value to curr.next and advance that list's pointer.
  • We advance the curr pointer.
  • Once the loop finishes (because one list is fully exhausted), we attach the remaining part of the other list directly to curr.next.
This runs in linear O(n + m) time (where n and m are the lengths of the two lists) using only O(1) auxiliary space.

Step-by-Step Execution Walkthrough

Let's trace the algorithm on list1 = 1 -> 3 and list2 = 2 -> 4:

  1. Step 1 (Initialization): Create a dummy node ListNode dummy = new ListNode(-1) and set curr = dummy.
    • list1 = [1, 3], list2 = [2, 4]
    • Merged list: dummy -> null
  2. Step 2 (Iteration 1): Compare list1.val (1) and list2.val (2).
    • Since 1 < 2, we link curr.next = list1.
    • Advance list1 = list1.next (which is node 3).
    • Advance curr = curr.next (which is node 1).
    • Merged list: dummy -> 1.
  3. Step 3 (Iteration 2): Compare list1.val (3) and list2.val (2).
    • Since 3 >= 2, we link curr.next = list2.
    • Advance list2 = list2.next (which is node 4).
    • Advance curr = curr.next (which is node 2).
    • Merged list: dummy -> 1 -> 2.
  4. Step 4 (Iteration 3): Compare list1.val (3) and list2.val (4).
    • Since 3 < 4, link curr.next = list1.
    • Advance list1 = list1.next (which is null).
    • Advance curr = curr.next (which is node 3).
    • Merged list: dummy -> 1 -> 2 -> 3.
  5. Step 5 (Exhaustion & Splicing): The loop terminates because list1 is null.
    • We check if any list remains. Yes, list2 has remaining nodes (node 4).
    • We splice the remainder: curr.next = list2.
    • Merged list: dummy -> 1 -> 2 -> 3 -> 4.
  6. Step 6 (Completion): The method returns dummy.next, which is the head of the sorted merged list: 1 -> 2 -> 3 -> 4 -> null.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • ListNode dummy = new ListNode(-1);: Serves as a constant anchor point at the beginning, so we don't have to write complex conditional logic to set the head of the merged list.
  • curr.next = (list1 != null) ? list1 : list2;: Instantly attaches the remainder of whichever list is not empty, avoiding unnecessary element-by-element copy loops.
  • return dummy.next;: Returns the actual start of the sorted list, skipping the dummy node placeholder.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class MergeTwoSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val; }
    }

    // Optimized - Iterative Merge - O(n + m)
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void main(String[] args) {
        MergeTwoSortedLists solver = new MergeTwoSortedLists();
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        System.out.println("--- Merge Two Sorted Lists Demonstration ---");
        ListNode result = solver.mergeTwoLists(l1, l2);
        printList(result);
    }

    private static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + (curr.next != null ? " -> " : ""));
            curr = curr.next;
        }
        System.out.println();
    }
}

Conclusion

Solving the Merge Two Sorted Lists problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.