SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

Remove the Nth Node From the End Visualizer

Move fast n + 1 steps ahead of slow. Then move both until fast falls off the end: slow now sits just before the node to remove.

Start the Remove the Nth Node From the End simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Add a dummy node D before the head. Both pointers start at D.
  2. Move fast ahead (1 of 3) to 1.
  3. Move fast ahead (2 of 3) to 2.
  4. Move fast ahead (3 of 3) to 3.
  5. fast is now 3 nodes ahead of slow. Keep that gap and move both.
  6. Move both: slow to 1, fast to 4.
  7. Move both: slow to 2, fast to 5.
  8. Move both: slow to 3, fast to null.
  9. fast fell off the end, so slow is just before the target. Point 3 past 4.
  10. Return dummy.next. The list is now 1 → 2 → 3 → 5.

Try it with your own input →

Remove the Nth node from the end in Java, Python, C++, C and JavaScript

ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode dummy = new ListNode(0, head);
  ListNode fast = dummy, slow = dummy;
  for (int i = 0; i <= n; i++) fast = fast.next;
  while (fast != null) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next
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) {
    slow = slow->next;
    fast = fast->next;
  }
  slow->next = slow->next->next;
  return dummy.next;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
  struct ListNode dummy = { 0, head };
  struct ListNode *fast = &dummy, *slow = &dummy;
  for (int i = 0; i <= n; i++) fast = fast->next;
  while (fast) {
    slow = slow->next;
    fast = fast->next;
  }
  struct ListNode* gone = slow->next;
  slow->next = gone->next; free(gone);
  return dummy.next;
}
function removeNthFromEnd(head, n) {
  const dummy = { val: 0, next: head };
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;
  while (fast !== null) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}

In an interview

LeetCode 19, Remove Nth Node From End of List. The same gap trick finds the middle node (876) and the kth node from the end.

The dummy node (D) before the head means removing the head needs no special case. Interviewers look for it.

More lists, stacks & queues