Remove Nth Node From End of List

Difficulty: Medium

Problem

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

Follow up: Could you do this in one pass?

Example

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: The 2nd node from the end is node(4). After removing it, the list becomes [1,2,3,5].

Brute-force approach — Count Length Then Remove

First traverse the entire list to count its length L. Then traverse again to the (L - n)th node and remove the next node.

Steps

  1. Traverse the list to count total length L
  2. Calculate target position: L - n
  3. Traverse to position (L - n - 1) to find the node before the target
  4. Skip the target node: node.next = node.next.next
  5. Return head (use dummy for edge cases)

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Requires two passes through the list
  • Not suitable for streaming data where length is unknown

Optimal approach — One-Pass Two-Pointer Technique

Key insight: Maintain a gap of n+1 between two pointers so when fast hits null, slow is right before the target node.

Use two pointers with a gap of n+1 between them. When the fast pointer reaches null, the slow pointer is right before the node to remove. This does it in a single pass.

Steps

  1. Create dummy node, point both slow and fast to it
  2. Advance fast pointer n+1 steps
  3. Move both pointers until fast reaches null
  4. slow.next is the target — skip it
  5. Return dummy.next

Time complexity: O(n) · Space complexity: O(1)