Remove Nth Node From End of List

Medium
2002.

Remove Nth Node From End of List

Remove Nth Node From End of List is a medium coding problem on two pointers, asked in Amazon, Google, Microsoft and Meta interviews.

Given the head of a singly linked list and an integer n, remove the n-th node counted from the end of the list (the last node is the 1st from the end), and return the head of the resulting list.

Example 1

Input
head = [1,2,3,4,5], n = 2
Output
[1,2,3,5]
Explanation
The 2nd node from the end holds 4.

Example 2

Input
head = [1], n = 1
Output
[]
Explanation
Removing the only node leaves an empty list.

Example 3

Input
head = [1,2], n = 2
Output
[2]
Explanation
The node to remove can be the head itself.

Constraints

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

Follow-up: Can you do it in one pass?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Nth Node From End of List — Problem & Solution

Remove Nth Node From End of List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Nth Node From End of List is a medium coding problem on two pointers, asked in Amazon, Google, Microsoft and Meta interviews.

  • Difficulty: Medium
  • Topics: Two Pointers
  • Asked at: Amazon, Google, Microsoft, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the head of a singly linked list and an integer n, remove the n-th node counted from the end of the list (the last node is the 1st from the end), and return the head of the resulting list.

Example 1

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: The 2nd node from the end holds 4.

Example 2

Input: head = [1], n = 1
Output: []
Explanation: Removing the only node leaves an empty list.

Example 3

Input: head = [1,2], n = 2
Output: [2]
Explanation: The node to remove can be the head itself.

Constraints

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

Follow-up: Can you do it in one pass?

Hints for Remove Nth Node From End of List

  1. Hint 1

    Counting the length first and then walking length - n steps works, in two passes.

  2. Hint 2

    For one pass, keep two pointers exactly n nodes apart; when the front one reaches the end, the back one is just before the node to delete.

  3. Hint 3

    Start both pointers at a dummy node placed before the head, so deleting the head needs no special case.

How to solve Remove Nth Node From End of List

Two pointers with a fixed gap: move fast n nodes ahead of slow, then advance both until fast is on the last node. slow then sits right before the node to remove.

Approach

  1. Create a dummy node pointing at head; set fast = slow = dummy.
  2. Advance fast n times.
  3. While fast.next is not null, advance both fast and slow.
  4. Unlink with slow.next = slow.next.next and return dummy.next.

Why it works

With the dummy at position 0 and the list at positions 1..L, fast ends at position L and slow at L − n, the predecessor of position L − n + 1, which is the n-th node from the end.

Complexity

  • Time — O(L)
  • Space — O(1)

Pitfalls

  • When n equals the length, the head itself is removed — the dummy node makes that the ordinary case.
  • Stopping when fast is null (instead of fast.next) leaves slow one node too far.

Reference solution

Python

from typing import Optional

def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

Java

public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) fast = fast.next;
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
}

C++

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode *fast = &dummy, *slow = &dummy;
    for (int i = 0; i < n; i++) fast = fast->next;
    while (fast->next) { fast = fast->next; slow = slow->next; }
    slow->next = slow->next->next;
    return dummy.next;
}

JavaScript

var removeNthFromEnd = function(head, n) {
    var dummy = new ListNode(0, head), fast = dummy, slow = dummy;
    for (var i = 0; i < n; i++) fast = fast.next;
    while (fast.next !== null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique