AlgoMaster Logo

Remove Nth Node From End of List

Ashish

Ashish Pratap Singh

medium

Problem Description

Solve it on LeetCode

Approaches

1. Two Pass

Intuition:

The basic idea behind this approach is to determine the length of the linked list and then remove the (L-n+1)'th node from the beginning (where L is the length of the list). In the first pass, we calculate the total length of the linked list. Then in the second pass, we traverse the list again up to the (L-n+1)'th node and remove it.

Steps:

  1. Traverse the entire list to compute the total length L.
  2. Find the node just before the (L-n+1)th node (this will be at position (L-n)) and change its next pointer to skip the nth node from the end.
  3. Return the head of the modified list.

Code:

2. One Pass using Two Pointers

Intuition:

We can improve our solution by using two pointers with a gap of n nodes between them. By moving both pointers simultaneously until the fast one reaches the end, the slow pointer will be just before the node we want to remove.

Steps:

  1. Initialize two pointers: fast and slow both pointing to a dummy node ahead of head.
  2. Move fast pointer n+1 steps forward to maintain a gap of n between slow and fast.
  3. Move both fast and slow pointers until fast pointer reaches the end.
  4. The slow pointer will be at the node just before the target node. Adjust its next pointer to skip the nth node from the end.
  5. Return the head of the modified list.

Code:

Prev:

Next: