Merge Two Sorted Lists: Combining Linked Lists in Order

The "Merge Two Sorted Lists" problem is a fundamental exercise in linked list manipulation, focusing on merging two sorted lists into one.

Problem Statement

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example

• Input: List1 1 -> 2 -> 4, List2 1 -> 3 -> 4
• Output: Merged List 1 -> 1 -> 2 -> 3 -> 4 -> 4

Iterative Solution

class ListNode {
    val: number;
    next: ListNode | null;

    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.next = (next === undefined ? null : next);
    }
}

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let dummyHead = new ListNode(0);
    let current = dummyHead;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // Attach the remaining part of l1 or l2
    current.next = l1 ? l1 : l2;

    return dummyHead.next;
}

Breaking Down the Solution

• Initialize a Dummy Head: Start with a dummy head to simplify edge cases and maintain a reference to the head of the merged list.
• Iterate Through Both Lists: Compare nodes from both lists, appending the smaller node to the merged list.
• Handle Remaining Nodes: Once one of the lists is exhausted, attach the remaining part of the other list to the merged list.
• Return Merged List: The next of the dummy head points to the start of the merged list.

Conclusion

Merging two sorted linked lists is a common problem that demonstrates the importance of pointer manipulation in data structures. It's a key skill for many algorithms and applications involving linked lists.