How do you solve Remove Nth Node From End of List?

Create a dummy node pointing to the head to handle edge cases gracefully. Initialize two pointers: left at dummy and right at head. Move right pointer n steps forward. Then move both pointers simultaneously until right reaches the end. Adjust left.next to skip the target node. Return dummy.next as the new head.

What pattern does Remove Nth Node From End of List use?

The Pattern: Two Pointers (Fixed Gap) The Heuristic: Maintain two pointers separated by a fixed gap equal to n; when the leading pointer reaches the end, the trailing pointer is positioned just before the target node, enabling single-pass removal.

Remove Nth Node From End of List — Two Pointers

Q: What is the time complexity of Remove Nth Node From End of List?

O(n). Each pointer traverses the list at most once. The right pointer moves n steps initially, and then both pointers move together until the end, resulting in a single pass through the list.

Problem

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

The number of nodes in the list is at least 1
1 ≤ n ≤ the length of the list

Example

Input: head = [1,2,3,4,5], n = 2

Output: [1,2,3,5]

A naive approach would first compute the length of the list, then remove the (length - n + 1)th node from the start, requiring two passes. The optimal approach uses two pointers spaced n nodes apart. Initially, the right pointer advances n steps ahead. Then both pointers move forward simultaneously until the right pointer reaches the end. At this point, the left pointer is just before the target node. Removing the target node is done by adjusting the left pointer's next reference. This single-pass approach efficiently removes the nth node from the end without computing the list length explicitly.

Approach

Straightforward Solution

A straightforward solution involves two passes: first, traverse the list to find its length; second, traverse again to the (length - n)th node and remove the next node. This approach is O(2n) time and requires two traversals.

Core Observation

The key insight is that the nth node from the end is the (length - n + 1)th node from the start. By maintaining two pointers separated by n nodes, when the leading pointer reaches the end, the trailing pointer is positioned just before the node to remove.

Path to Optimal

Preview

To optimize to a single pass, use two pointers. Advance the right pointer n steps ahead…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Create a dummy node pointing to the head to handle edge cases gracefully. Initialize two pointers: left at dummy and right at head…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer traverses the list at most once. The right pointer moves n steps initially, and then both pointers move together until the end, resulting in a single pass through the list.

Space

O(1)

Only a fixed number of pointers and variables are used, regardless of input size, resulting in constant auxiliary space.

Solution

Python

1class Solution:
  def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
      dummy = ListNode(0, head)
      left = dummy
      right = head
6
      while n > 0 and right:
          right = right.next
          n -= 1
      
      while right:
          left = left.next
          right = right.next
      
      left.next = left.next.next
      return dummy.next

Step-by-Step Solution

1

Create Dummy Node and Initialize Two Pointers

3dummy = ListNode(0, head)
4left = dummy
5right = head

Objective

To set up a dummy node before the head and initialize two pointers to prepare for the fixed-gap traversal.

Key Insight

The dummy node acts as a sentinel to handle edge cases uniformly, such as removing the head node. Initializing the left pointer at dummy and the right pointer at head sets the stage for maintaining a gap of n nodes between them, which is critical for locating the target node in one pass.

Interview Quick-Check

Core Logic

The dummy node ensures that the left pointer can safely move to the node before the one to remove, even if that node is the head.

State & Boundaries

Left starts at dummy, right starts at head, establishing the initial positions for the two-pointer gap.

2

Advance Right Pointer by n Steps to Establish Gap

To move the right pointer n nodes ahead to create a fixed gap between left and right pointers.

3

Move Both Pointers Until Right Reaches End

To advance both pointers simultaneously until the right pointer reaches the end of the list.

4

Remove Target Node and Return Updated List Head

To unlink the target node from the list and return the new head.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 15 Critical

left.next = left.next.next

Unlink the target node by skipping it in the list.

This pointer adjustment is the critical step that removes the target node without needing to traverse the list again, enabling the single-pass solution.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why is it necessary to use a dummy node at the start of the list?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Remove Nth Node From End of List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Remove Nth Node From End of List drill

or drill a free problem

1	`class Solution:`
2	`def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:`
3	`dummy = ListNode(0, head)`
4	`left = dummy`
5	`right = head`
6
7	`while n > 0 and right:`
8	`right = right.next`
9	`n -= 1`
10
11	`while right:`
12	`left = left.next`
13	`right = right.next`
14
15	`left.next = left.next.next`
16	`return dummy.next`