Week 3 · Linked List

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list. The runner uses sorted value lists; the real interview version relinks nodes.

Easy Linked List Week 3 Practice runner

Frame the problem

Both inputs are sorted.
One or both lists can be empty.
The merged output must preserve sorted order.

1. Reveal example inputs and outputs

Example 1

Input:

merge_two_lists([
  1,
  2,
  4
], [
  1,
  3,
  4
])

Output:

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

Example 2

Input:

merge_two_lists([], [
  0
])

Output:

[
  0
]

2. Brute force first

Why not concatenate and sort? Which sorted-input property supports one linear pass?

3. Reveal the insight ladder

Use a dummy head.
Compare current nodes.
Append the smaller node and advance that list.
Append the remaining tail when one list ends.

4. Dry run before code

[1,2,4] and [1,3,4].
Take 1, 1, 2, 3, 4, 4.
Return [1,1,2,3,4,4].

5. Reveal final Python solution

def merge_two_lists(list1, list2):
    result = []
    i = j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    return result + list1[i:] + list2[j:]

Complexity: Time O(n + m). Pointer version uses O(1) extra space beyond output links.

Interview narration

The dummy head avoids special-casing the first node.
The smaller current value is always safe to append.
The remaining tail is already sorted.

Common traps

Not advancing the selected pointer.
Dropping the tail.
Overcomplicating head initialization.

Follow-up drills

1. Can you reuse existing nodes?

Yes. Set tail.next to the selected node and advance that source pointer; no new nodes are required.

2. What changes for descending lists?

Reverse the comparison or normalize the inputs. The merge invariant must match the sort order.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.