Merge two sorted Lists

Problem Link

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list and return the head of the merged list.

Examples

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

Intuition

This is a standard merge step from merge sort.

Since both input lists are already sorted, we can traverse both lists using two pointers and select the smaller current node each time to build the final merged list.

Approach: Iterative Merge with Dummy Node

Create a dummy node (-1 as placeholder) and set a tail pointer to it.
Traverse both list1 and list2:
- Append the smaller node to tail.next
- Move the corresponding list pointer forward
- Advance tail
After the loop, append the remaining nodes from the non-null list.
Return dummy.next as the head of the merged list.

Java Code

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1); // dummy head
        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 part
        if (list1 != null) tail.next = list1;
        if (list2 != null) tail.next = list2;

        return dummy.next;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	`O(n + m)` where `n` and `m` are lengths of `list1` and `list2`
Space Complexity	`O(1)` (no extra data structures used, just pointer manipulation)

Dry Run

Input:

list1 = [1, 3, 5], list2 = [2, 4, 6]

Steps:

Compare 1 and 2 → take 1 → move list1
Compare 3 and 2 → take 2 → move list2
Compare 3 and 4 → take 3 → move list1
Compare 5 and 4 → take 4 → move list2
Compare 5 and 6 → take 5 → move list1
list1 is null → append remaining list2 (6)

Result: 1 → 2 → 3 → 4 → 5 → 6

Alternate Approach: Recursive

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;

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

Time: O(n + m)
Space: O(n + m) due to recursive call stack

Conclusion

This problem demonstrates the importance of the two-pointer technique in linked list problems. The dummy node trick simplifies edge case handling and is widely used in merge and append operations.