Merge Two Sorted Lists

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Examples

The brute-force approach

Collect all values from both lists into an array, sort the array, then build a new linked list from the sorted values.

values = []
while list1: values.append(list1.val); list1 = list1.next
while list2: values.append(list2.val); list2 = list2.next

values.sort()    # ← discards the sorted property you already had

dummy = ListNode(0)
cur = dummy
for v in values:
    cur.next = ListNode(v)
    cur = cur.next

return dummy.next

Sorting an already-partially-sorted collection throws away free information. The sort step is O(n log n) when you could merge in O(n) by exploiting the fact that both lists are already sorted.

Spotting the pattern

This is a Linked List problem. The key question to ask yourself:

Can I use a pointer on each list and always pick the smaller front node to build the merged result?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.