remove-nth-from-end

Difficulty: Medium · Topic: Linked List · Practice it on parikshan: /practice/remove-nth-from-end/start

The story

Slack's message stream is a linked list of messages per channel, growing at the tail. The user invokes "delete the 5th message from the bottom" from a moderation tool. The client can iterate the list once because the stream sits in memory, but it does not know the total length cheaply (the channel could have 1.2 million messages, and the count is on the server). The deletion has to happen in one pass.

remove-nth-from-end is the canonical version of "remove the k-th-from-tail node in one pass without first measuring the list". The technique is a fixed-gap two-pointer: start two walkers with a gap of k, then advance both at the same speed until the leading walker hits the end. The trailing walker is at the node before the target.

What's actually being asked

You are given the head of a singly linked list and an integer k, where 1 <= k <= n. Remove the k-th node from the end of the list and return the resulting list. k = 1 removes the last node; k = n removes the head.

The naive approach

Two passes. First pass: count n. Second pass: walk n - k steps from the head to reach the predecessor of the target node. O(n) time, O(1) space. Correct, easy.

Why bother with one pass? Two reasons. One: in some streaming contexts (Slack's example, Kafka tail-of-partition) you cannot afford to walk the list twice because each walk takes the lock. Two: the gap-based two-pointer is the right mental model for every "k from the tail" problem, including palindrome-linked-list's mid-finding and linked-list-cycle-ii's offset math.

The key insight

Two pointers, slow and fast. Position fast exactly k steps ahead of slow. Then advance both one step at a time. When fast falls off the end (becomes null), slow is exactly k positions from the end, i.e., on the node to remove.

The trick is removing the head case. If k = n, you want to remove the head, but slow would have to land before the head, which does not exist in a singly linked list. The fix is the Linked List primer's first rule: use a dummy head sentinel whose next is the real head. Now slow can land on the dummy, and slow.next = slow.next.next correctly cuts out the original head.

Step-by-step approach

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def remove_nth_from_end(head, k):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(k):                  # open the gap
        fast = fast.next
    while fast.next is not None:        # advance in lockstep
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next          # excise the target
    return dummy.next

Loop invariant in English: fast is exactly k positions ahead of slow. When fast is at the last node (fast.next is None), slow is k nodes before the last node, which is one node before the target. Reassigning slow.next skips the target and the rest of the list flows through unchanged.

Why while fast.next is not None, not while fast is not None? Because we want slow to land on the predecessor of the target, not the target itself. If we let fast fall fully off (become null), slow would land on the target and we would not be able to splice. Stopping when fast.next is null leaves both pointers one step earlier in the list.

Worked example

Input: 1 -> 2 -> 3 -> 4 -> 5, k = 2. Expected: remove the 4 (second from end). Result: 1 -> 2 -> 3 -> 5.

Step	slow	fast
Initial	dummy	dummy
After gap (k=2)	dummy	2
Iter 1	1	3
Iter 2	2	4
Iter 3	3	5
`fast.next` is null	exit

slow is on node 3. slow.next = slow.next.next skips node 4. Result: 1 -> 2 -> 3 -> 5. ✓

Counter-case: k = n = 5 (remove the head). After the gap, fast is at node 5 (5 steps from dummy). The lockstep loop runs zero times (fast.next is null immediately). slow is still at dummy. dummy.next = dummy.next.next removes the head. Return dummy.next = 2. ✓

Counter-case: single-node list [42], k = 1. After the gap, fast is at node 42. The lockstep loop runs zero times. slow is at dummy. dummy.next = dummy.next.next makes dummy.next = null. Return null. ✓

The dummy makes head-removal and non-head removal use the same code path. No branches.

Complexity

Time: O(n). One pass with a constant-gap walker.
Space: O(1). Two pointers and the dummy.

Common pitfalls

No dummy head: without it, head-removal needs a special case (if k == n: return head.next) and the code splits into two cases that drift apart over time. The dummy fixes it in two lines.
while fast is not None instead of while fast.next is not None: slow lands on the target, not the predecessor. The splice line then tries slow.next = slow.next.next from the wrong position and either crashes or removes the wrong node.
Opening the gap with range(k + 1) instead of range(k): a gap of k + 1 makes slow land two before the target, and the splice removes the wrong node.
k = 0 or k > n: the spec excludes these, but agent-generated code that adds a defensive if k <= 0: return head adds a footgun. Trust the spec; only validate at system boundaries (the Linked List cluster is internal, not user input).

Where this shows up in the enterprise

Slack / Discord moderation tools: removing the k-th message from the end of a channel feed without re-counting.
Kafka tail compaction: dropping the k-th-from-tail record in a partition during compaction.
CockroachDB delete-from-end queries: the same shape on sorted-by-time tables.
Git history rewrite: git rebase -i HEAD~k is morally "remove the k-th-from-tip commit"; the implementation is gap-based.
Apple HealthKit data retention: dropping the oldest k samples when retention rolls forward; if the list grew unbounded, this exact algorithm.
Stripe webhook retry queue: removing the k-th-from-tail failed delivery without re-walking the queue.

The fingerprint: a stream with no random access, a need to remove a node at a fixed offset from the tail, and a desire to do it in one pass while holding the lock for as little time as possible.

Variants you'll see elsewhere

middle-of-linked-list: variable-speed two-pointer; this problem is the fixed-gap cousin.
kth-from-end: return the node's value instead of removing it. Same gap technique without the splice.
linked-list-cycle-ii: gap-based reasoning finds the cycle start.
rotate-list: rotate by k; needs n and the (n - k)-th node from the head, computable with the same gap idea.
swap-nodes-in-linked-list: swap the k-th from head and k-th from end; two-pointer with gap.

If reverse-linked-list is the three-pointer pattern and middle-of-linked-list is the variable-speed pattern, this is the fixed-gap pattern. The three together cover almost every linked-list manipulation problem in the interview canon.

How parikshan turns this into a learning loop

Recommended sequence on parikshan:

Solve reverse-linked-list and middle-of-linked-list first.
In practice mode, AI off, code the dummy + gap template. Run public tests.
The dynamic private tests will throw: k = 1, k = n, single-node list, two-node list with k = 2. The single-node case and k = n case are where templates without a dummy head die.
Re-solve without the dummy and feel the branching. The dummy is two extra lines; the no-dummy version is six extra lines and one silent bug.
Ask the parikshan assistant in practice mode: "would two-pass be acceptable here?" The answer in production-prep is "it depends on the lock cost". A real senior conversation, free of penalty.

In the AI-integrated workspace

Generated code for remove-nth-from-end is correct about 80% of the time. The 20% failure breakdown:

12%: omits the dummy head; head-removal crashes with NoneType has no attribute next.
5%: opens the gap by k + 1 instead of k; removes the wrong node.
3%: uses while fast is not None instead of while fast.next is not None; same wrong-node bug.

Verification ritual on every agent-generated removal:

Find the dummy. If there is no dummy, ask the agent to refactor with one. The refactor will be cleaner; the agent will not push back.
Trace by hand on [1, 2], k = 2 (remove head, two-node list). This is the smallest case where the bugs surface.
Read the loop bound. Must be fast.next is not None, not fast is not None.

These three checks take 20 seconds. The senior engineers who run them in 20 seconds are the ones who never approve a wrong moderation-tool PR. parikshan trains the reflex against a Linked List cluster built specifically to expose these failures.