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.

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 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)

Pseudocode

function removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy
    for i = 0 to n:
        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
  • Advance the fast pointer n+1 steps ahead
  • 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.

Related problems

Keep practising