TIC
The Interns Company

Remove Nth Node From End of List

MediumAcceptance: 39.8%
Linked ListTwo Pointers

Problem Statement

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

Constraints:

  • The number of nodes in the list is sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Input Format:

  • head: The head of a linked list
  • n: The position from the end to remove (1-indexed)

Output Format:

  • The head of the modified linked list

Examples:

Example 1:

Input:

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

Output:

[1,2,3,5]

Explanation:

After removing the second node from the end, the linked list becomes 1->2->3->5.

Example 2:

Input:

head = [1], n = 1

Output:

[]

Explanation:

The list has only one node, and we remove it.

Example 3:

Input:

head = [1,2], n = 1

Output:

[1]

Explanation:

After removing the first node from the end, the linked list becomes 1.

Solutions

Two Pointers Approach

Time: O(L) where L is the length of the linked list
Space: O(1) as we only use two pointers regardless of list size

Use two pointers with a gap of n nodes. When the fast pointer reaches the end, the slow pointer will be at the node to be removed.

Two-Pass Approach

Time: O(L) where L is the length of the linked list
Space: O(1) as we only use constant extra space

First pass to count the length of the list, second pass to find and remove the (length-n+1)th node from the beginning.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. Input: head = [1,2,3,4,5], n = 2
  2. Create a dummy node: dummy -> 1 -> 2 -> 3 -> 4 -> 5
  3. Initialize fast and slow pointers at dummy
  4. Move fast pointer n+1 (3) steps: fast = 4
  5. Now start moving both pointers until fast reaches null:
  6. fast = 4, slow = dummy
  7. fast = 5, slow = 1
  8. fast = null, slow = 2
  9. At this point, slow.next (3) is the node to be removed
  10. Update slow.next to slow.next.next: 2 -> 4
  11. Return dummy.next: 1 -> 2 -> 4 -> 5

Hints

Hint 1
Maintain two pointers and update one with a delay of n steps.
Hint 2
Use a dummy node to handle edge cases where the head might be removed.
Hint 3
Consider the case where you need to remove the head of the list.
Hint 4
One pass approach is possible with two pointers spaced n nodes apart.

Video Tutorial

Remove Nth Node From End of List - Two Pointers Approach

YouTube•Learn the Remove Nth Node From End of List solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the two pointers moving through the linked list, with the gap between them indicating the position to remove.

Key visualization elements:

  • current fast pointer
  • current slow pointer
  • node to be removed

Asked By

AmazonMicrosoftFacebookGoogleAppleBloombergAdobe

Implementation Notes

The two-pointer technique is elegant because it allows for a one-pass solution. Using a dummy node simplifies edge cases, especially when removing the head of the list.