Log inSign up
mediumLeetCodeNot Started

Remove Nth Node From End of List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a linked list, remove the nth 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]
Explanation: The 2nd node from the end is node 4. After removing it, the list is [1, 2, 3, 5].

Example 2:

Input: head = [1], n = 1
Output: []
Explanation: The only node is removed, leaving an empty list.

Example 3:

Input: head = [1,2], n = 1
Output: [1]
Explanation: The last node (node 2) is removed, leaving [1].

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

1. Two-Pass Length Counting

Intuition

1. Traverse from head to null to count total length L. 2. Create a dummy node pointing to head. 3. The node to remove is at index L - n from dummy (0-indexed from dummy). 4. Advance a pointer L - n times from dummy, reaching the predecessor node. 5. Rewire curr.next = curr.next.next. 6. Return dummy.next.

When to apply: Intuitive baseline when two-pointer gap synchronization is unfamiliar.

Algorithm

  1. Find total node count L.
  2. Create dummy node pointing to head.
  3. Traverse (L - n) steps from dummy.
  4. Bypass target: curr.next = curr.next.next.
  5. Return dummy.next.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* removeNthFromEnd(ListNode* head, int n) {
14 int length = 0;
15 ListNode* curr = head;
16 while (curr != nullptr) {
17 length++;
18 curr = curr->next;
19 }
20
21 ListNode dummy(0, head);
22 curr = &dummy;
23 for (int i = 0; i < length - n; ++i) {
24 curr = curr->next;
25 }
26
27 ListNode* toDelete = curr->next;
28 curr->next = curr->next->next;
29 delete toDelete;
30
31 return dummy.next;
32 }
33};
34
35int main() {
36 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
37 Solution sol;
38 ListNode* res = sol.removeNthFromEnd(head, 2);
39 while (res != nullptr) {
40 std::cout << res->val << " ";
41 res = res->next;
42 }
43 std::cout << std::endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(L) — Pass 1 takes L steps to count length. Pass 2 takes (L - n) steps to reach predecessor. Total operations = 2L - n = O(L).
  • Space complexity: O(1) — Only requires integer counters and temporary pointers: O(1) auxiliary space.

2. Recursive Post-Order Backtracking Counter

Intuition

1. Base case: If node == null, return counter 0. 2. Recurse for node.next. 3. Counter increments on returning: count = 1 + helper(node.next). 4. If count == n + 1, we are at the predecessor of target, so set node.next = node.next.next. 5. Handle the edge case where the head itself is the nth node from the end by checking if total length == n.

When to apply: When demonstrating recursive call-stack manipulation without explicit forward iteration.

Algorithm

  1. Wrap head in dummy node.
  2. Helper recursive function returns 1-based distance from the end of the list.
  3. When child returns n, parent removes child node.
  4. Return dummy.next.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12private:
13 int removeHelper(ListNode* node, int n) {
14 if (!node) return 0;
15 int count = removeHelper(node->next, n) + 1;
16 if (count == n + 1) {
17 ListNode* toDel = node->next;
18 node->next = node->next->next;
19 delete toDel;
20 }
21 return count;
22 }
23
24public:
25 ListNode* removeNthFromEnd(ListNode* head, int n) {
26 ListNode dummy(0, head);
27 removeHelper(&dummy, n);
28 return dummy.next;
29 }
30};
31
32int main() {
33 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
34 Solution sol;
35 ListNode* res = sol.removeNthFromEnd(head, 2);
36 while (res != nullptr) {
37 std::cout << res->val << " ";
38 res = res->next;
39 }
40 std::cout << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(L) — Visits every node once going down the call stack and once returning up.
  • Space complexity: O(L) recursion stack — Recursion stack depth equals length L.

3. One-Pass Two Pointers with Fast/Slow Gap

Intuition

1. Create sentinel dummy with dummy.next = head. 2. Initialize fast = dummy, slow = dummy. 3. Move fast ahead by n + 1 steps so that fast and slow are separated by n nodes. 4. Move both fast and slow one node at a time until fast == null. 5. slow.next is now the Nth node from the end. Rewire: slow.next = slow.next.next. 6. Return dummy.next.

When to apply: The definitive, optimal single-pass algorithm asked in FAANG/top tech interviews.

Algorithm

  1. Initialize dummy with dummy.next = head.
  2. Set fast = dummy, slow = dummy.
  3. Advance fast by n + 1 steps.
  4. Advance fast and slow together until fast == null.
  5. Bypass target: slow.next = slow.next.next.
  6. Return dummy.next.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
We need to advance fast pointer by n + 1 = 3 steps
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

We need to advance fast pointer by n + 1 = 3 steps.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* removeNthFromEnd(ListNode* head, int n) {
14 ListNode dummy(0, head);
15 ListNode* fast = &dummy;
16 ListNode* slow = &dummy;
17
18 // Advance fast by n + 1 steps
19 for (int i = 0; i <= n; ++i) {
20 fast = fast->next;
21 }
22
23 // Move both until fast reaches null
24 while (fast != nullptr) {
25 fast = fast->next;
26 slow = slow->next;
27 }
28
29 // slow is now before the target node
30 ListNode* toDelete = slow->next;
31 slow->next = slow->next->next;
32 delete toDelete;
33
34 return dummy.next;
35 }
36};
37
38int main() {
39 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
40 Solution sol;
41 ListNode* res = sol.removeNthFromEnd(head, 2);
42 while (res != nullptr) {
43 std::cout << res->val << " ";
44 res = res->next;
45 }
46 std::cout << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(L) single pass — fast traverses exactly L + 1 steps from dummy to null in a single linear pass.
  • Space complexity: O(1) auxiliary — Only two pointer variables (fast and slow) are maintained, achieving O(1) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Two-Pass Length CountingO(L)O(1)First traverse the list to compute its total length L. Then traverse to index (L - n) and remove the next node.High time complexity
2.Recursive Post-Order Backtracking CounterO(L)O(L) recursion stackRecursively dive to the end of the list and count backward on the return call stack. When index equals n, bypass the node.—
3.One-Pass Two Pointers with Fast/Slow GapOptimalO(L) single passO(1) auxiliaryAdvance a fast pointer n + 1 steps from a dummy head sentinel. Then move both fast and slow pointers simultaneously until fast reaches null. Slow will be pointing directly to the predecessor of the target node.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Failing to use a dummy sentinel node, causing crash or special case bug when n == length (i.e. deleting the head node).

Pitfall 2:

Advancing fast by n steps instead of n + 1 steps when starting from dummy, which lands slow on the target node itself rather than its predecessor.

Pitfall 3:

Not handling edge cases with 1 node list where n = 1.

Back to DSA Sheet