Drop Nth From End
Problem
Given the head of a singly linked list and a number n, remove the node that sits n positions from the end and return the head of the resulting list. Counting starts at the last node, so n equal to 1 removes the tail. You may assume n never exceeds the length of the list, and the goal is a single traversal.
Examples
Input: head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5
Why: the second node from the end is 4Input: head = 1 -> 2, n = 2
Output: 2
Why: edge case, the removed node is the head itselfInput: head = 9, n = 1
Output: empty
Why: edge case, removing the only node empties the listHints
0 / 3
Counting the length first and then walking again is correct but touches the list twice. Think about how a fixed distance between two travellers encodes a position from the end.
If one pointer starts n nodes ahead of another and both move at the same speed, the trailing pointer has a known relationship to the end when the leading one arrives there.
Advance a leading pointer n steps, then move both pointers together until the leader reaches the last node. The trailing pointer now sits just before the victim, so relink it to skip one node. Start both from a placeholder before the head so removing the head needs no special branch.
Solution
Two pointers separated by a gap of n nodes move in lockstep, so when the leader reaches the last node the follower stands exactly one node before the target. Starting both at a dummy node placed before the head means removing the first node is handled by the same relink as any other position. That gives a single traversal instead of one pass to measure the length and another to cut. Time is O(L) for list length L, and space is O(1).
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def drop_nth_from_end(head, n):
dummy = Node(0, head) # lets head removal use the same relink
lead = lag = dummy
for _ in range(n): # open a gap of exactly n nodes
lead = lead.next
while lead.next: # slide both until the leader hits the tail
lead, lag = lead.next, lag.next
lag.next = lag.next.next # lag sits right before the victim
return dummy.next
print(dump(drop_nth_from_end(build([1, 2, 3, 4, 5]), 2))) # -> [1, 2, 3, 5]
print(dump(drop_nth_from_end(build([1, 2]), 2))) # -> [2]
print(dump(drop_nth_from_end(build([9]), 1))) # -> []Stuck on the idea rather than the code? Fast and Slow Pointers covers it.