7.2 Remove Nth Node From End of List

7.2.1 Problem Metadata

7.2.2 Description

Given the head of a linked list, remove the nth node from the end of the list and return its head.

7.2.3 Examples

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

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

7.2.4 Constraints

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

7.2.5 Solution - Two Pointers with Gap

7.2.5.1 Walkthrough

This solution uses a two-pointer technique with a fixed gap to find the n-th node from the end in a single pass.

Core Strategy:

  1. Create a gap of n+1 nodes between two pointers
  2. When the fast pointer reaches the end, the slow pointer is at the node before the target
  3. Skip over the target node by updating slow.next

Why n+1 gap? We need the slow pointer to stop at the node before the one we want to remove, so we can update slow.next to skip the target.

Example: Remove 2nd from end in [1,2,3,4,5]:

Initial: dummy → 1 → 2 → 3 → 4 → 5 → null
         first
         second

After n+1 (3) moves of first:
         dummy → 1 → 2 → 3 → 4 → 5 → null
                           first
         second

Move both until first is null:
         dummy → 1 → 2 → 3 → 4 → 5 → null
                                     first (null)
                      second (at node 3)

Remove: second.next = second.next.next
Result: 1 → 2 → 3 → 5

7.2.5.2 Analysis

  • Time Complexity: O(n) - Single pass through the list
  • Space Complexity: O(1) - Only pointer variables used

7.2.5.3 Implementation Steps

  1. Create a dummy node pointing to head (handles edge case of removing head).
  2. Initialize both first and second pointers at dummy.
  3. Move first forward n+1 times to create the gap.
  4. Move both pointers until first reaches null.
  5. Skip the target node: second.next = second.next.next.
  6. Return dummy.next.

7.2.5.4 Code - Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = dummy, second = dummy;
    for (int i = 0; i <= n; i++) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}