Coding problem · Medium · Linked List

Remove Nth Node From End of List

Medium Algorithms & data structures Seen at Meta, Amazon, Microsoft

Given the head of a linked list, remove the n-th node from the end of the list and return its head. Try to do it in one pass.

Example 1

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

Example 2

Input: head = [1], n = 1
Output: []

Constraints

1 <= n <= list length

Hints

Hint 1

Advance a fast pointer n steps first, then move fast and slow together until fast reaches the end.

Hint 2

A dummy node handles removing the head.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Keep a gap of n nodes between two pointers starting at a dummy node. When fast hits the last node, slow sits just before the node to remove; unlink it with slow.next = slow.next.next.

Reference solution

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy, slow = dummy;
  for (let 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;
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode = dummy, slow: ListNode = dummy;
  for (let 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;
}

def remove_nth_from_end(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, slow = fast.next, slow.next
    slow.next = slow.next.next
    return dummy.next

<?php

function removeNthFromEnd(?ListNode $head, int $n): ?ListNode
{
    $dummy = new ListNode(0, $head);
    $fast = $slow = $dummy;
    for ($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;
}

class Solution {
    public 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;
    }
}