Remove Nth Node From End of List

Why it belongs on this sheet

This is the classic example of using a fixed pointer gap to avoid computing length first.

Pattern

Gap of n nodes

Approach

Use a dummy node before the head. Move fast ahead by n + 1 steps, then move both pointers together until fast finishes. slow.next is the node to remove.

Java solution

class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode slow = dummy;
    ListNode fast = dummy;

    for (int i = 0; i <= n; i++) {
      fast = fast.next;
    }

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

    slow.next = slow.next.next;
    return dummy.next;
  }
}

Complexity

• Time: O(n)
• Space: O(1)

Interview note

The dummy node handles deletion of the head without special casing.