LeetCode 19 · Medium · Linked List

Remove Nth Node From End of List

Given the head of a linked list, unlink the n-th node counted from the end and return the head. Do it in one pass, without first measuring the length.

O(L)time · one pass
O(1)space
gap of ntwo pointers + dummy

1–10 integers, −99 to 99 · n from 1 to the list length

Linked list dashed node = dummy before head · right (blue) runs n nodes ahead of left · row 2 = the unlinked node

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode left = dummy; ListNode right = head; while (n > 0) { // open a gap of n nodes right = right.next; n--; } while (right != null) { // slide the gap to the end left = left.next; right = right.next; } left.next = left.next.next; // skip the target return dummy.next;}
n
—
left
—
right
—
list
—

Why it works

  1. Brute force walks twice: count the length L, then walk L − n nodes and unlink the next one. Still O(L), but two passes; the follow-up asks for one.
  2. Keep a fixed gap. right starts n nodes ahead of left, and both move together. When right falls off the end (null), left is exactly n + 1 nodes from it: the node just before the target.
  3. One pass, two pointers: right visits every node once and left trails it, so O(L) time and O(1) space.
  4. Pitfall: removing the head. When n equals the length, the target has no predecessor. The dummy node gives it one, so left.next = left.next.next works with no special case. Return dummy.next, not head, which may be the removed node.
  5. Pitfall: the gap is n, not n − 1. left starts on the dummy, one step behind head, so it stops on the predecessor instead of the target itself.