Remove Nth Node From End of List

Difficulty: Medium

Problem

You are given the head of a singly linked list and an integer n. Delete the node that sits n positions from the tail (the last node counts as position 1), then return the head of the resulting list.

Constraints: 1 <= n <= the number of nodes in the list, so the list is never empty and n never goes past the head.

Follow up: Could you do this in one pass?

Example

Input: head = [10,20,30,40], n = 3
Output: [10,30,40]
Explanation: Counting from the tail, 40 is 1st, 30 is 2nd and 20 is 3rd. Removing node(20) leaves [10,30,40].

Brute-force approach, Count Length Then Remove

First traverse the entire list to count its length L. Then start at the dummy and hop L - n times. That reaches the box before the target (box number L - n from the front, with the head as number 1). Remove the next node.

Steps

  1. Traverse the list to count total length L
  2. Calculate the hops: L - n (the box before the target is number L - n from the front, the dummy is number 0)
  3. Starting at the dummy, hop L - n times to reach the node before the target
  4. Skip the target node: node.next = node.next.next
  5. Return dummy.next (the dummy handles removing the head)

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: Keep n boxes between slow and fast (fast starts n + 1 steps ahead), so when fast hits null, slow is right before the target node.

Use two pointers with n boxes between them, so fast starts n + 1 steps ahead of slow. 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 n + 1 steps (n boxes between slow and fast)
  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)

Pseudocode

function removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy
    repeat n + 1 times:
        fast = fast.next
    while fast != null:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

Hints

  • Use a dummy node to handle edge cases like removing the head
  • Start fast n + 1 steps ahead of slow, so there are n boxes between them
  • When fast reaches null, slow is right before the target node

Complexity questions

What is the time complexity of the two-pass approach?

O(n). Two passes through the list: O(n) + O(n) = O(2n) = O(n).

What is the space complexity of the two-pass approach?

O(1). Only a few pointer variables are used, giving O(1) space.

What is the time complexity of the one-pass two-pointer approach?

O(n). We traverse the list once with the fast pointer, giving O(n) time.

What is the space complexity of the one-pass approach?

O(1). Only two pointers and a dummy node, giving O(1) space.

Check your understanding of Remove Nth Node From End of List

In the list [1,2,3,4,5], which node is the 2nd from the end?

Node with value 4. Counting from the end: 1st from end is 5, 2nd from end is 4. So the 2nd node from the end has value 4.

After removing the 2nd node from the end of [1,2,3,4,5], what is the result?

[1,2,3,5]. The 2nd node from the end is 4. Removing it gives [1,2,3,5].

For a list with only one node [1], and n = 1, what is the expected result?

An empty list (the only node is removed). The 1st node from the end is the only node (value 1). Removing it leaves an empty list.

The code ends with return dummy.next. Why not return head?

When the head itself is removed, head would still point at the removed node. When n equals the length, the head is the node we remove. slow stays on the dummy and the dummy now skips the head, but the variable head still points at the removed node. dummy.next always holds the real first node.

Related problems

Keep practising