Skip to main content

37. Remove Nth Node From End of List

mediumAsked at Ola

Remove the nth node from the end of a linked list in one pass.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • Number of nodes is sz
  • 1 <= sz <= 30
  • 1 <= n <= sz

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
[]

Approaches

1. Two-pass count

Count length first; walk to (length-n-1) and unlink.

Time
O(n)
Space
O(1)
let len = 0; let n2 = head;
while (n2) { len++; n2 = n2.next; }
const dummy = { next: head }; let t = dummy;
for (let i=0;i<len-n;i++) t = t.next;
t.next = t.next.next;
return dummy.next;

Tradeoff:

2. Two pointers in one pass

Advance fast by n, then move both until fast reaches the end; slow.next is the target.

Time
O(n)
Space
O(1)
function removeNthFromEnd(head, n) {
  const dummy = { next: head };
  let slow = dummy, fast = dummy;
  for (let i = 0; i < n; i++) fast = fast.next;
  while (fast.next) { slow = slow.next; fast = fast.next; }
  slow.next = slow.next.next;
  return dummy.next;
}

Tradeoff:

Ola-specific tips

Ola engineers love the one-pass two-pointer trick; tie it to trimming the n-th oldest event from a fixed-sized in-memory dispatch queue.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Remove Nth Node From End of List and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →