Merge Lists and Classic Interview Problems
32 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Most linked list interview problems combine three moves: a dummy node, two pointers and a few relinks. This lesson applies them to merging, removing from the end, adding numbers, intersections and sorting.
Merge two sorted lists
Merging sorted lists is joining two sorted lists into one sorted list by repeatedly taking the smaller front node. It reuses the nodes and takes O(n + m) time.
Two sorted lists can become one by repeatedly taking the smaller front node. A dummy node and a tail pointer build the result, and no node is copied.
def merge(a, b): dummy = tail = Node(0) while a and b: if a.value <= b.value: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.nextExample 1 · Merge two sorted lists
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def merge(a, b): dummy = tail = Node(0) while a and b: if a.value <= b.value: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next
print(to_list(merge(build([1, 4, 9]), build([2, 3, 10, 12]))))[1, 2, 3, 4, 9, 10, 12]
What this code does
- Each round takes the smaller front value, so 1, 2, 3, 4, 9 come out in order and the leftover 10, 12 is attached at the end.
- The nodes are reused, so no new nodes are made except the dummy.
Example 2 · Brute force and the library way
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
import heapq
def merge_sorted_values(a, b): return build(list(heapq.merge(to_list(a), to_list(b))))
print(to_list(merge_sorted_values(build([1, 4, 9]), build([2, 3, 10]))))[1, 2, 3, 4, 9, 10]
What this code does
- Copy both lists to Python lists, merge them with
heapq.merge, and build a new list. That is short but makes new nodes. - In an interview, write the pointer version. In real Python code, normal lists with
sortedorheapq.mergeare simpler.
When one list runs out, the other is already sorted, so tail.next = a or b attaches it in one step. Time is O(n + m) and extra space is O(1).
Remove the n-th node from the end
You do not know the length, so keep two pointers n steps apart. When the leading one reaches the end, the trailing one stands just before the node to remove.
def remove_nth_from_end(head, n): dummy = Node(0, head) lead = trail = dummy for _ in range(n): lead = lead.next while lead.next: lead = lead.next trail = trail.next trail.next = trail.next.next return dummy.nextExample 3 · Remove the n-th node from the end
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def remove_nth_from_end(head, n): dummy = Node(0, head) lead = trail = dummy for _ in range(n): lead = lead.next while lead.next: lead = lead.next trail = trail.next trail.next = trail.next.next return dummy.next
print(to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)))print(to_list(remove_nth_from_end(build([1, 2, 3]), 3)))[1, 2, 3, 5] [2, 3]
What this code does
- Removing the 2nd from the end deletes 4. Removing the 3rd from the end of a 3-node list deletes the head itself.
- The dummy node is what makes the second call work without a special case.
The dummy node makes removing the head work like any other node. This is one pass, O(n) time and O(1) space, with no need to count the length first.
Add two numbers stored as lists
A number can be stored one digit per node, lowest digit first. Add the lists node by node, like school addition, carrying 1 to the next node when a sum reaches 10.
def add(a, b): dummy = tail = Node(0) carry = 0 while a or b or carry: total = carry + (a.value if a else 0) + (b.value if b else 0) carry, digit = divmod(total, 10) tail.next = Node(digit) tail = tail.next a = a.next if a else None b = b.next if b else None return dummy.nextExample 4 · Add two numbers stored in lists
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def add(a, b): dummy = tail = Node(0) carry = 0 while a or b or carry: total = carry + (a.value if a else 0) + (b.value if b else 0) carry, digit = divmod(total, 10) tail.next = Node(digit) tail = tail.next a = a.next if a else None b = b.next if b else None return dummy.next
print(to_list(add(build([2, 4, 3]), build([5, 6, 4]))))print(to_list(add(build([9, 9]), build([1]))))[7, 0, 8] [0, 0, 1]
What this code does
- The lists hold 342 and 465 with the lowest digit first, and the sum 807 is stored the same way as 7, 0, 8.
- For 99 + 1 the sum is 100 stored as 0, 0, 1: the leftover carry creates a last node.
divmod(total, 10) gives the carry and the digit together. The or carry in the loop adds a final node when a carry is left over, as in 99 + 1. Python integers have no overflow, but this is the way to add numbers that arrive as chains.
Find where two lists meet
Intersection node is a node that two lists share, so both chains continue through the same object from that point. It is found by identity (is), not by equal values.
Two lists can share the same tail nodes. Walk a pointer on each list, and when one reaches the end, restart it on the other list. Both then walk the same total distance and meet at the shared node.
def intersection(a, b): p, q = a, b while p is not q: p = p.next if p else b q = q.next if q else a return pExample 5 · Two lists that share a tail
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def intersection(a, b): p, q = a, b while p is not q: p = p.next if p else b q = q.next if q else a return p
shared = Node(8, Node(10))a = Node(1, Node(2, shared))b = Node(5, shared)print(intersection(a, b).value)print(intersection(a, Node(7)))8 None
What this code does
- The lists are 1, 2, 8, 10 and 5, 8, 10. They share the nodes from 8 on, so 8 is the meeting node.
- A separate list with no shared node gives None.
If there is no shared node, both become None together and the loop ends with None. Use is: an intersection means the same node object, not just equal values.
Sort a linked list
A linked list cannot be indexed, so merge sort fits it well. Split at the middle with slow and fast pointers, sort each half, then merge the halves with merge.
def sort_list(head): if head is None or head.next is None: return head slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next second, slow.next = slow.next, None return merge(sort_list(head), sort_list(second))Example 6 · Sort a list by merge sort
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def merge(a, b): dummy = tail = Node(0) while a and b: if a.value <= b.value: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next
def sort_list(head): if head is None or head.next is None: return head slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next second, slow.next = slow.next, None return merge(sort_list(head), sort_list(second))
print(to_list(sort_list(build([40, 10, 30, 20, 50]))))[10, 20, 30, 40, 50]
What this code does
- Each call splits the list in two, sorts the halves and merges them, so the work is O(n log n).
- The shortcut
build(sorted(to_list(head)))is shorter and also O(n log n), but uses O(n) extra space and makes new nodes.
fast starts one node ahead, so slow ends on the first middle and both halves are smaller than the whole. Time is O(n log n). The recursion is only log n levels deep.
Next step
Check your understanding
12 quick questions