Merge Two Sorted Lists

L6 Medium Linked List

Concept

Merging keeps a placeholder head so the result is easy to build, then repeatedly attaches whichever front node is smaller.

The heads of two sorted linked lists are given. Merge the two lists so the result is a single sorted list containing every node of both. Return its head.

Examples

▸ list1 = [1, 2, 4], list2 = [1, 3, 4]

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

▸ list1 = [], list2 = []

→ []

▸ list1 = [], list2 = [0]

→ [0]

Progressive Hints

Hint 1 · Nudge

Repeatedly attach the smaller front node to your growing result.

Hint 2 · Plan

Compare the two front nodes, attach the smaller one to the result tail, and advance only that list. Keep going until one list is empty, then attach whatever remains of the other.

Hint 3 · Approach

dummy head node; tail = dummy. While both lists are non-empty: attach the smaller of the two heads and advance it. Attach whichever list still has nodes. Return dummy.next.

Output

// Run your code to see the output here.