Merge Two Sorted Lists

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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = [] Output: []

Example 3:

Input: list1 = [], list2 = [0] Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Approach: Iterative Merge with Dummy Node (Optimal Solution)

Algorithm

1. Create a dummy node to serve as the head of the merged list
2. Use a tail pointer that always points to the last node of the merged list
3. While both lists are non-empty, append the smaller head node to tail
4. When one list is exhausted, append the remainder of the other list
5. Return dummy.next as the new head

Key Insight

A dummy head simplifies the code by avoiding special handling for the first node. Since the lists are already sorted, merging is just a repeated “pick the smaller head” operation.

Time & Space Complexity

• Time Complexity: O(m + n) - each node is visited once
• Space Complexity: O(1) - only constant extra space, reuses existing nodes

Java Implementation

public class MergeTwoSortedLists {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * Merge two sorted linked lists into one sorted list.
     * @param list1 Head of the first sorted list
     * @param list2 Head of the second sorted list
     * @return Head of the merged sorted list
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }

        // Append the remaining nodes of the non-empty list
        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }

        return dummy.next;
    }

    // Helper method to build a list from an array
    public static ListNode buildList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode curr = head;
        for (int i = 1; i < values.length; i++) {
            curr.next = new ListNode(values[i]);
            curr = curr.next;
        }
        return head;
    }

    // Helper method to print a list
    public static void printList(ListNode head) {
        System.out.print("[");
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) {
                System.out.print(", ");
            }
            curr = curr.next;
        }
        System.out.println("]");
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        ListNode list1 = buildList(new int[]{1, 2, 4});
        ListNode list2 = buildList(new int[]{1, 3, 4});
        System.out.print("Input: list1 = ");
        printList(list1);
        System.out.print("Input: list2 = ");
        printList(list2);
        System.out.print("Output: ");
        printList(mergeTwoLists(list1, list2)); // Expected: [1, 1, 2, 3, 4, 4]

        // Test case 2
        System.out.print("Output: ");
        printList(mergeTwoLists(buildList(new int[]{}), buildList(new int[]{}))); // Expected: []

        // Test case 3
        System.out.print("Output: ");
        printList(mergeTwoLists(buildList(new int[]{}), buildList(new int[]{0}))); // Expected: [0]
    }
}

Example Walkthrough

For list1 = [1,2,4] and list2 = [1,3,4]:

1. dummy=0, tail=dummy. 1<=1, append list1’s 1. tail → 1, list1 → [2,4]
2. list2’s 1 < 2, append list2’s 1. tail → 1, list2 → [3,4]
3. list1’s 2 < 3, append 2. tail → 2, list1 → [4]
4. list2’s 3 < 4, append 3. tail → 3, list2 → [4]
5. list1’s 4 <= 4, append 4. tail → 4, list1 → null
6. list1 is null, append list2’s [4].

Merged list: [1, 1, 2, 3, 4, 4].

Recursive Approach

public static ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }

    if (list1.val <= list2.val) {
        list1.next = mergeTwoListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoListsRecursive(list1, list2.next);
        return list2;
    }
}

The recursive version merges the smaller head with the result of merging the remaining tails. It uses O(m + n) stack space.

Key Insights

1. Dummy Node: Eliminates edge-case handling for inserting the first node
2. In-Place Splicing: Reuses the existing nodes rather than creating new ones
3. Tail Attachment: Appending the remainder of a non-empty list is O(1) thanks to sorted order
4. Stable Merge: <= keeps the relative order of equal elements stable

The iterative dummy-node approach is the optimal solution, providing linear time complexity with constant space.