How do you remove the nth node from the end of a linked list in a single pass?
You use two pointers that are n nodes apart, and you move them both along together. When the front pointer reaches the end, the other one is on the node before the one you want to remove.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def remove_nth_from_end(head, n):
dummy = Node(0, head)
front = dummy
back = dummy
for _ in range(n):
back = back.next
while front.next is not None:
front = front.next
back = back.next
back.next = back.next.next
return dummy.next
So how does it work? You put a dummy node at the front, and you start both pointers on it. Then you move the back pointer forward n steps. Now the two pointers are n nodes apart.
And then you move them both along together until the front pointer reaches the end of the list. Because they started n apart and they always move together, the back pointer is now n nodes before the end, which is the node right before the one you want to remove.
the list 1 -> 2 -> 3 -> 4 -> 5
remove the 2nd from the end, which is the 4
the front pointer stops on the 5
the back pointer stops on the 3
and you cut the 4 out
And the dummy node is what saves you from the awkward cases. When you want to remove the last node, the back pointer has to be on the node before it, and without the dummy there is no node before the head in the empty case. With the dummy the back pointer always has a node to point at, so the removal line is always the same.
And the complexity is O of n for the time, because the two passes over the pointers together are bounded by the length of the list, and O of 1 for the space.
So the rule to remember is this. Start the two pointers n apart, move them together, and the second one ends up on the node before the one you want.
The last question in this topic shows the case of removing the last node.