Remove nth Node from End of List

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

Problem Statement

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

Constraints

• The number of nodes in the list is k.
• 1 ≤ k ≤ 10³
• −10³ ≤ Node.value ≤ 10³
• 1 ≤ n ≤ k

Examples

Example 1

Input:

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

Output: [1, 2, 3, 5]

Example 2

Input:

• head = [1]
• n = 1

Output: []

Example 3

Input:

• head = [1, 2]
• n = 2

Output: [2]

Solution

The trick here is very simple: we use two pointers, both starting at the head of the list.

Steps

• We move the fastPointer forward by n steps first. This creates a gap of n nodes between fastPointer and slowPointer.
• After moving fastPointer forward by n steps, we check: is fastPointer now null?
  • If it is, that means the list only has exactly n nodes, and the node we need to remove is the head itself. So we simply return head.next.
• Otherwise, we move both pointers forward together, one step at a time, until fastPointer reaches the last node in the list (fastPointer.next === null).
• Because of the initial gap of n nodes, this guarantees that slowPointer now sits right before the node we need to remove.
• We remove the target node by simply skipping over it: slowPointer.next = slowPointer.next.next.
• Finally, we return head, which still points to the start of our (now modified) list.

Code

var removeNthFromEnd = function (head, n) {

    let fastPointer = head;
    let slowPointer = head;

    for (let i = 0; i < n; i++) {
        fastPointer = fastPointer.next;
    }

    if (!fastPointer) return head.next;

    while (fastPointer.next !== null) {
        fastPointer = fastPointer.next;
        slowPointer = slowPointer.next;
    }

    slowPointer.next = slowPointer.next.next;

    return head;
};

Complexity

• Time complexity: O(N)
• Space complexity: O(1)