TL;DR
Two-pointer splice with a dummy head — O(n + m) time, O(1) space (iterative).
Approach 1 — Brute force: collect, sort, rebuild
Ignore that the inputs are sorted: dump every value into a Python list, sort it, and build a fresh linked list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def mergeTwoLists(
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()
dummy = ListNode()
tail = dummy
for v in vals:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
Complexity: O((n+m) log(n+m)) time, O(n+m) space.
At 50 nodes per list this passes, but it wastes the sortedness of the inputs, allocates all-new nodes when the problem asks you to splice the existing ones, and pays an unnecessary log factor.
Approach 2 — Iterative two-pointer merge with a dummy head
The next node of the answer is always the smaller of the two current front nodes. This is the merge step of merge sort: the combine phase that stitches two sorted runs together in linear time. A dummy head removes the special case of appending the first node.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def mergeTwoLists(
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
tail always points at the last node of the built result, and each step links the smaller front node onto tail.next:
flowchart LR
subgraph in1 [list1]
A1[1] --> A2[2] --> A4[4]
end
subgraph in2 [list2]
B1[1] --> B3[3] --> B4[4]
end
subgraph out [merged result]
D[dummy] --> M1[1] --> M2[1] --> M3[2] --> M4[3] --> M5[4] --> M6[4]
end
Walkthrough on list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4:
| compare | take | result so far |
|---|
| 1 vs 1 | list1’s 1 (ties go left) | 1 |
| 2 vs 1 | list2’s 1 | 1 -> 1 |
| 2 vs 3 | 2 | 1 -> 1 -> 2 |
| 4 vs 3 | 3 | 1 -> 1 -> 2 -> 3 |
| 4 vs 4 | list1’s 4 | 1 -> 1 -> 2 -> 3 -> 4 |
| list1 empty | attach rest of list2 | 1 -> 1 -> 2 -> 3 -> 4 -> 4 |
Complexity: O(n + m) time, O(1) extra space — nodes are relinked in place.
Approach 3 — Recursive merge
The merge has a recursive definition: the merged list is the smaller head followed by the merge of everything that remains. The base case is one list being empty.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def mergeTwoLists(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = mergeTwoLists(list1.next, list2)
return list1
list2.next = mergeTwoLists(list1, list2.next)
return list2
Walkthrough on the same example: the first call picks list1’s 1 and recurses on (2->4, 1->3->4); that call picks 1 and recurses on (2->4, 3->4); then 2, then 3, then 4, then list1 is empty so 4 (the rest of list2) is returned and the stack unwinds, wiring 1 -> 1 -> 2 -> 3 -> 4 -> 4.
Complexity: O(n + m) time, O(n + m) space for the call stack — fine at 100 total nodes, but the iterative version is the safe default on long lists (Python’s default recursion limit is 1000).
Common pitfalls
- Forgetting
tail.next = list1 if list1 else list2 after the loop — the leftover tail of the longer list silently disappears.
- Returning
dummy instead of dummy.next, adding a phantom 0 node to the front.
- Building the result with
new ListNode(...) copies when the problem asks you to splice the given nodes.
- Using
< instead of <= doesn’t break correctness here, but <= keeps the merge stable (equal elements keep their original relative order), which interviewers sometimes probe.
Pattern takeaway
When two inputs are each sorted, the answer’s next element is always one of two candidates — a single comparison per output node gives a linear merge. And any time you build a linked list front-to-back, start with a dummy head: it collapses the empty-result and first-node special cases into the general one.