Skip to main content

19. Remove Nth Node From End of List

medium

Remove the nth node from the end of a linked list in one pass. The two-pointer-with-gap technique avoids first counting the length, and the dummy head sidesteps the 'remove the actual head' edge case.

By Sam K., 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

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 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
[]

Example 3

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two passes is allowed but the bonus version asks for one.

Hint 2

Use two pointers separated by n nodes. When the leader hits null, the follower is at the node to remove.

Hint 3

Use a dummy head so removing the actual head node isn't a special case.

Solution approach

Reveal approach

One pass with two pointers and a dummy head. Create dummy = ListNode(0, head); set lead = follow = dummy. Advance lead by n + 1 steps. Then advance both pointers together until lead is null. At that moment, follow points at the node BEFORE the one to remove. Rewire follow.next = follow.next.next to drop it. Return dummy.next (handles removing the original head correctly). O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • two-pointers
  • dummy-head

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Bloomberg

More Linked Lists practice problems

See all Linked Lists problems →