19. Remove Nth Node From End of List

Time: O(n)

Space: O(1)

Intuition

To find the nth node from the end without knowing the list length, use a two-pointer gap trick: if fast is exactly n steps ahead of slow, then when fast reaches the tail, slow is precisely at the node we want to remove. A dummy node before head lets us handle removing the head itself cleanly.

Algorithm

1Create a dummy node pointing to head; initialise both fast and slow at dummy.
2Advance fast n+1 steps forward (so the gap between slow and fast is n+1).
3Move both fast and slow one step at a time until fast == null.
4Now slow.next is the node to delete. Set slow.next = slow.next.next.
5Return dummy.next.

Example Walkthrough

Input: head = [1->2->3->4->5], n = 2

1.dummy->1->2->3->4->5. Advance fast 3 steps: fast=3, slow=dummy.
2.Move both: fast=4, slow=1. Move both: fast=5, slow=2. Move both: fast=null, slow=3.
3.slow.next (node 4) is the 2nd from end. slow.next = node 5.
4.List becomes 1->2->3->5.

Output: [1, 2, 3, 5]

Common Pitfalls

•Advance fast n+1 (not n) steps so slow stops one node BEFORE the target.
•The dummy node is essential: without it, removing the head (n == list length) requires a special case.

19.cs

// Approach: Use a dummy node before head to cleanly handle the edge case of removing the head itself.
// Advance the fast pointer n+1 steps ahead of slow (both starting at dummy).
// Move both pointers one step at a time until fast reaches null.
// At that point slow.next is the node to delete; redirect slow.next = slow.next.next.
// Single pass — no need to know the list length or make a second traversal.
// Time: O(n) Space: O(1)

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode RemoveNthFromEnd(ListNode head, int n)
    {
        ListNode start = new ListNode();
        start.next = head;
        ListNode slow = start;
        ListNode fast = start;
        for (int i = 1; i <= n; i++)
        {
            fast = fast.next;
        }

        while (fast.next != null)
        {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return start.next;
    }
}

Was this solution helpful?