PPractick

The problem

A logging service keeps recent log entries in a singly linked list and occasionally needs to delete the entry N positions from the end, for example the second-to-last. Counting the length first and then walking to position L − N takes two passes. The one-pass trick: start two pointers together, move the first N steps ahead, then move both until the first reaches the last node. The second pointer is then just before the node to remove. A dummy node in front of the head makes removing the head itself (N = length) no different from any other case.

Example: 1 -> 2 -> 3 -> 4 -> 5, N = 2 → 1 -> 2 -> 3 -> 5.

Function signature

Node* removeNthFromEnd(Node* head, int n);  // 1 <= n <= length; returns the new head

Test cases

Input (list, n)	Output list	Explanation
(1 -> 2 -> 3 -> 4 -> 5, 2)	1 -> 2 -> 3 -> 5	Removes 4
(1, 1)	(empty)	Removes the only node
(1 -> 2, 1)	1	Removes the tail
(1 -> 2, 2)	2	Removes the head
(1 -> 2 -> 3, 3)	2 -> 3	Removes the head of a longer list

(Confirm: n is valid (1 ≤ n ≤ length); the removed node is freed; one pass is the goal.)

How interviewers phrase it

• "Remove the n-th node from the end of the list" (LeetCode 19).
• "Can you do it in one pass?"
• Related: find the k-th node from the end, rotate a list by k.

Clarifying questions to ask

1. Is n always valid?
2. Should the removed node be freed?
3. One pass required?

Follow-ups to expect

1. "Why the dummy node?"
2. "Why move the fast pointer n steps first?"
3. "What's the two-pass approach?"
4. "Complexity?"

Related questions

• Detect a loop in LL Medium
• Find the starting point in LL Medium
• Length of loop in LL Medium
• Check if LL is palindrome or not Medium
• Delete the middle node in LL Medium
• Find the intersection point of Y LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in