Task example: Merge Two Sorted Lists

Given the first nodes of two chains sorted in non-decreasing order, reconnect their existing nodes into one sorted chain. Return its first node. Keep every node and its value; do not create replacement nodes. The two input chains are separate and contain no cycles.

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

Array notation shows node values, not Python list arguments. The editor supplies ListNode with val and next. Your function receives two nodes or None and returns a node or None.

View LeetCode 21

01 / Collect & sort - baseline

Collect & sort: video explanation

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

Prefer reading? Follow the steps below.

Follow both input chains and collect references to their nodes. Sort those references by node.val, keeping all duplicates.
Use a temporary dummy node and tail. Attach each sorted node after tail, then move tail forward. The dummy is not part of the returned result.
Set the final tail.next to None and return dummy.next. Both empty inputs return None. Node values remain unchanged.

Time complexity · O(N log N)

Let N = n + m be the total number of nodes. Collection and relinking take O(N); general-purpose sorting gives an O(N log N) upper bound. Python may exploit existing ordered runs.

Space complexity · O(N)

The reference list and Python sorting workspace need O(N) extra space. Original nodes are reused.

PYTHONLive code trace

02 / Iterative merge - optimal space

Iterative merge: video explanation

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

Prefer reading? Follow the steps below.

Create a dummy node and tail. While both inputs are nonempty, compare their front values. The smaller front is the next smallest remaining node.
Attach the smaller node after tail. On a tie, choose list1. Advance only that input, then advance tail. Keep both equal-valued nodes.
When one input ends, attach the entire remaining chain with tail.next = list1 or list2. Return dummy.next. No more comparisons are needed.

Using the sorted input order avoids the reference array and general-purpose sorting. The iterative merge guarantees linear worst-case time and constant extra space.

Time complexity · O(N)

For N = n + m nodes, worst-case time is O(N). Each comparison consumes one node; the remaining chain attaches in O(1). If an input is empty, the function can finish immediately.

Space complexity · O(1)

The dummy node and a fixed number of references use O(1) extra space. There is no reference array and no recursion stack.

PYTHONLive code trace