01 Jan 2024•Easy•C++ / Python / TypeScript

Merge Two Sorted Lists

Splice two sorted linked lists into one sorted list.

Problem

Given the heads of two sorted linked lists, merge them into one sorted list made by splicing together the existing nodes, and return its head.

Approach

Start from a dummy node so the head of the merged list needs no special case.

Compare the current nodes of both lists, attach the smaller one to the result, and advance that list. When one list runs out, attach the rest of the other list in one step, since it is already sorted.

The solution files below implement this approach in C++, Python and TypeScript.

Complexity

Time: O(n + m).
Space: O(1): the existing nodes are relinked, not copied.

Edge cases

Either list can be empty.
Equal values can come from either list; taking from the first keeps the merge stable.

Solution files

Python•merge-two-sorted-lists/synced-solution.py

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1; list1 = list1.next
            else:
                cur.next = list2; list2 = list2.next
            cur = cur.next
        cur.next = list1 or list2
        return dummy.next

C++•merge-two-sorted-lists/synced-solution.cpp

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy; ListNode* cur = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; }
            else { cur->next = l2; l2 = l2->next; }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

TypeScript•merge-two-sorted-lists/synced-solution.ts

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    while (list1 && list2) {
        if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; }
        else { cur.next = list2; list2 = list2.next; }
        cur = cur.next!;
    }
    cur.next = list1 ?? list2;
    return dummy.next;
}