Merge Two Sorted Lists

EASY✓ CHIP-TIMEDLC #21 — FULL STATEMENT ↗

The drill: Weave two already-sorted linked lists into one sorted list, reusing the existing nodes instead of allocating new ones.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two singly linked lists arrive, each already sorted in non-decreasing order on its own, and the job is to weave them into a single sorted list.

The existing nodes should be reused and rewired rather than copied into fresh ones — the merge is a matter of redirecting pointers, not rebuilding values from scratch.

Either list can be empty, in which case the other list is simply handed back untouched as the answer, and ties between equal values can be resolved in either order.

EX 01

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

→ [1, 2, 3, 4, 5, 6]

PERFECT INTERLEAVE

EX 02

list1 = [] · list2 = []

→ []

EX 03

list1 = [] · list2 = [0]

→ [0]

each list holds up to a few thousand nodes
both input lists are individually sorted in non-decreasing order
either list, or both, may be empty
existing nodes are relinked, not copied into new ones

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Both lists are sorted — so the next node of the answer is always one of just two candidates.

HINT 2 THE STRUCTURE

A dummy head node kills every special case about starting the result.

HINT 3 ONE STEP FROM THE ANSWER

Advance whichever list offered the smaller head; when one runs out, the other attaches whole — no node-by-node copying of the tail.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE DUMMY-HEAD WEAVEPATTERN · DUMMY-HEAD WEAVElist1 = 1 → 3 → 5 · list2 = 2 → 4 → 6

STEP 1

Two sorted lists: 1→3→5 and 2→4→6. Splice a dummy-head result by always taking the smaller of the two current heads.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/merge-two-sorted-lists.py — RACE PACE

LANG ▸

PACE ▸

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

TIME O(M+N)SPACE O(1)PYTHON · RACE PACE · 14 LN

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        vals = []
        for head in (list1, list2):
            node = head
            while node:
                vals.append(node.val)
                node = node.next
        vals.sort()
        rebuilt = None
        for v in reversed(vals):
            rebuilt = ListNode(v, rebuilt)
        return rebuilt

TIME O((M+N) LOG(M+N))SPACE O(M+N)PYTHON · TRAINING PACE · 13 LN

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        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;
        }
        tail.next = list1 != null ? list1 : list2;
        return dummy.next;
    }
}

TIME O(M+N)SPACE O(1)JAVA · RACE PACE · 18 LN

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode n = list1; n != null; n = n.next) {
            vals.add(n.val);
        }
        for (ListNode n = list2; n != null; n = n.next) {
            vals.add(n.val);
        }
        Collections.sort(vals);
        ListNode rebuilt = null;
        for (int i = vals.size() - 1; i >= 0; i--) {
            rebuilt = new ListNode(vals.get(i), rebuilt);
        }
        return rebuilt;
    }
}

TIME O((M+N) LOG(M+N))SPACE O(M+N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED