Command Palette

Search for a command to run...

Hectal
Problem 8.5 · Linked ListsMedium

Remove Nth Node From End

PatternDummy Head and MergingFast and Slow Pointers

What it teaches: Two pointers with a fixed gap of n find the node before the target in one pass; a dummy head handles removing the first node.

Practise it on judges as “Remove Nth Node From End of List”.

The problem

Remove the n-th node from the end of the list and return its head.

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]

Constraints

  • 1 ≤ size ≤ 30
  • 1 ≤ n ≤ size

Pattern clues in the wording

  • → "From the end" in a singly linked list
  • → One pass asked
  • → The head itself might be removed

These clues point to Dummy Head and Merging: Start with a fake node before the real head so building, merging and deleting never need special cases for the first node.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        return dummy.next;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
head = [1,2,3,4,5]
n = 2
[1,2,3,5]
2
head = [1]
n = 1
[]
3
head = [1,2]
n = 1
[1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: gap pointers from a dummy · O(L)
1

Optimal: gap pointers from a dummy

Time O(L) Space O(1)

Both start at the dummy. Move fast n + 1 steps. Then move both until fast is null; slow is just before the node to delete. Skip it.

▶ Dry run: Keeping a gap of n + 1head = [1, 2, 3, 4, 5], n = 2
d
↑slow
1
2
3
↑fast
4
5
null

Step 1/4Both start at the dummy d. Move fast 3 steps (n + 1).

Approach 1
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head), slow = dummy, fast = dummy;
        for (int i = 0; i <= n; i++) fast = fast.next;     // n + 1 steps ahead
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Verdict: One pass, and the dummy handles n = length.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Removing the head (n = length)
  • Single node
  • Removing the last node (n = 1)

Mistakes people make

  • A gap of n instead of n + 1 (stops on the target, not before it).
  • Starting at head instead of the dummy, which breaks removing the head.

Interview

Follow-up questions

What if n might be larger than the list length?