5. Remove Nth Node From End of List

Description

Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

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

Example 2:
Input: head = [1], n = 1
Output: []

Example 3:
Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Approach - 2 pointer

• Create left and right pointer and left pointing to a block before head and right pointing to the nth element
• Left pointer to a new block because if you start with head you will reach the exact element but we need to reach an element before that
• Shift right pointer to the right to the nth node so as to create a window then loop till it reaches null and move left pointer too it will reach n-1 node from last then it is simple
• Time:O(n) Space:O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = head;
 
        while (n > 0) {
            right = right.next;
            n--;
        }
 
        while (right != null) {
            left = left.next;
            right = right.next;
        }
 
        left.next = left.next.next;
        return dummy.next;  // cannot return head as [1] should return []
    }
}

To remove the $n$-th node from the end of a singly-linked list, use either a two-pass length count or a two-pointer gap strategy.

Brute Force: Two-Pass Count Method

Find the total length of the list, then make a second pass to find and un-link the target node.

• Concept: If the total length is $L$, the node to delete is at index $(L-n+1)$ from the front. The node right before it is at index $(L-n)$.
• Algorithm:

1. Traverse the entire list once to count total nodes $L$.
2. Create a dummy node pointing to head to safely handle deleting the head node.
3. Traverse $L-n$ steps from dummy to reach the node before the target.
4. Skip the target node: curr.next = curr.next.next.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = 0;
        ListNode curr = head;
        
        // Pass 1: Find length
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        
        // Pass 2: Stop right before target
        curr = dummy;
        for (int i = 0; i < length - n; i++) {
            curr = curr.next;
        }
        
        // Delete target node
        curr.next = curr.next.next;
        return dummy.next;
    }
}
 

• Time Complexity: $O(L)$ (2 passes over the list).
• Space Complexity: $O(1)$.

---

Most Optimized & Easy to Remember: Fast & Slow Pointer Gap Method

Maintain a fixed gap of $n+1$ nodes between a fast and slow pointer so you can complete the removal in a single pass.

• Mental Model (The Gap Rule):

• If fast is $n+1$ steps ahead of slow, then when fast reaches null (end of list), slow will naturally be sitting 1 node before the node to delete.

• Algorithm:

1. Create a dummy node pointing to head and place both fast and slow on dummy.
2. Advance fast forward by $n+1$ steps.
3. Move both fast and slow forward one step at a time until fast hits null.
4. Disconnect target node: slow.next = slow.next.next.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
 
        // Step 1: Advance fast by n + 1 steps
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
 
        // Step 2: Walk both pointers together
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
 
        // Step 3: Skip target node
        slow.next = slow.next.next;
 
        return dummy.next;
    }
}
 

• Time Complexity: $O(L)$ (1 pass over the list).
• Space Complexity: $O(1)$.

The key is that for (int i = 0; i <= n; i++) runs $n+1$ times, not $n$ times. Counting from $0$ up to and including $n$ yields $(n+1)$ total steps.

Because fast takes $n+1$ steps while slow takes $0$ steps, the gap between fast and slow becomes $n+1$ nodes.

Why an $(n+1)$ gap lands slow on the predecessor node

When both pointers move together until fast hits null:

• **1 step behind null** = Last node ($1^{\text{st}}$ node from end)
• **$n$ steps behind null** = Target node ($n^{\text{th}}$ node from end)
• **$n+1$ steps behind null** = Predecessor node ($(n+1{)}^{\text{th}}$ node from end)

---

Step-by-Step Trace

List: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null | Remove $n=2$ (Node 4)

1. Create the $(n+1)=3$ Step Gap:

• Start: slow = dummy, fast = dummy
• i = 0: fast moves to 1
• i = 1: fast moves to 2
• i = 2: fast moves to 3

2. Slide both pointers until fast == null:

• Shift 1: fast at 4, slow at 1
• Shift 2: fast at 5, slow at 2
• Shift 3: fast at null, slow at 3

fast reached null, and slow stopped at **Node 3**—exactly one node before the target **Node 4**.

Doing $n+1$ steps upfront offsets slow by just enough to land on the node right before the one you need to delete, making slow.next = slow.next.next straightforward.

3 Rules to Remember for Interviews:

1. Always use a Dummy Node: Attaching dummy -> head avoids edge-case checks when deleting the very first node.
2. Move Fast First by $n+1$: Creating an $n+1$ gap places slow directly on the predecessor node.
3. Walk to Null: Move both until fast == null, then point slow.next to slow.next.next.