Merge two sorted linked lists
Picture
For 1→4 and 2→3, every later node is at least its list’s front. Compare 1 and 2.
Predict
Must we allocate new nodes to merge?
Walk through the small example
No. The minimum remaining node must be one of two current fronts.
Mental model and complete Python solution
Each chain offers its smallest remaining value at the front. The smaller front is globally safe; attach it and repeat the same question.
What the function promises: Return a nondecreasing chain reusing nodes. Inputs are disjoint, acyclic, and sorted.
class Node:
def __init__(self, value, next_node=None):
self.value, self.next = value, next_node
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def to_list(head):
answer = []
while head is not None:
answer.append(head.value)
head = head.next
return answer
def merge_lists(left, right):
dummy = tail = Node(None)
while left is not None and right is not None:
if left.value <= right.value:
tail.next, left = left, left.next
else:
tail.next, right = right, right.next
tail = tail.next
tail.next = left if left is not None else right
return dummy.next
assert to_list(merge_lists(build([1,4]), build([2,3]))) == [1,2,3,4]
Work and storage: O(n+m) time and O(1) auxiliary space.
When to recognize it: The minimum remaining node must be one of two current fronts.
Check before applying it: Reused nodes mutate the input chains; shared nodes or cycles violate the simple ownership contract.
Change one rule
Merge k sorted linked lists.
See what changes
Keep the current front of each nonempty list in a min-heap.
Connect
Two pointers: shrink one search space: Advance one of two monotone frontiers.
Merge sort: combine ordered halves: This merge is the combine step for linked-list merge sort.