Splice one chain into another
Cut a range of nodes out of one chain and plug a second chain into the gap, without copying anything. About 14 minutes.
Two anchors
Replacing places a to b of one chain with a second chain needs two anchors: the node just before place a, and the node just after place b. Everything between them goes away.
Point the first anchor at the head of the new chain. Walk to the new chain's last node and point it at the second anchor. The old section is unlinked, and the lists are joined without copying.
tail = list2
while tail.next:
tail = tail.next # last nodePlace 3 is the first removed node, so the before anchor is on place 2, which holds 8. Place 5 holds 2, so the after anchor is place 6, which holds 7.
Count to the anchors
Walk a-1 steps from a dummy node to reach the before anchor, because place a is the first removed node. Walk on to place b, then one more step, to get the after anchor.
If a is 1, the before anchor is the dummy and the new chain becomes the head. If b is the last place, the after anchor is nothing, and the new tail simply points at nothing.
before = dummy
for _ in range(a - 1):
before = before.nextWhat is the before anchor when the removed section starts at place 1?
- AThe dummy node in front of the head
- BThe head
- CNothing, so it cannot be done
Show the answer
The dummy node in front of the head. There is no real node before place 1, and the dummy stands in for it.
Replace a section with another list
You are given two linked lists, list1 and list2, and two places a and b (counting from 1, with a at most b). Remove the nodes of list1 from place a to place b, both included, and put the whole of list2 in their place. Return the head of the resulting list.
list1 = [10, 1, 13, 6, 9, 5], a = 3, b = 4, list2 = [1000000, 1000001] → [10, 1, 1000000, 1000001, 9, 5]
1 ≤ nodes in list1 ≤ 5,000 · 1 ≤ nodes in list2 ≤ 5,000 · 1 ≤ a ≤ b ≤ nodes in list1