Remove Nth Node from End of List in DSA C++

Mental Model

We want to remove a node counting from the end, so we use two pointers spaced apart to find it in one pass.

Analogy: Imagine two friends walking on a path where one starts ahead by n steps; when the front friend reaches the end, the other is right before the target to remove.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑         ↑
       slow      fast (n steps ahead)

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, remove 2nd node from end

Goal: Remove the 2nd node from the end, which is node with value 4

Step 1: Initialize two pointers slow and fast at dummy node before head

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑ fast ↑

Why: Dummy helps handle edge cases like removing head; both start together

Step 2: Move fast pointer 2 steps ahead

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑          fast ↑

Why: Fast pointer moves n steps ahead to create gap

Step 3: Move slow and fast pointers forward together until fast reaches end

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
           slow ↑               fast ↑

Why: When fast reaches end, slow is right before node to remove

Step 4: Remove node after slow by changing slow's next pointer

dummy -> 1 -> 2 -> 3 -> 5 -> null
           slow ↑

Why: Skip the target node to remove it from list

Result:

1 -> 2 -> 3 -> 5 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0); // dummy node before head
        dummy.next = head;
        ListNode* slow = &dummy;
        ListNode* fast = &dummy;

        // Move fast n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast->next; // advance fast pointer
        }

        // Move both pointers until fast reaches the end
        while (fast->next != nullptr) {
            slow = slow->next; // advance slow pointer
            fast = fast->next; // advance fast pointer
        }

        // Remove the nth node from end
        slow->next = slow->next->next; // skip target node

        return dummy.next; // return new head
    }
};

// Helper to print list
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << " -> null" << endl;
}

int main() {
    // Create list 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    ListNode* newHead = sol.removeNthFromEnd(head, 2);

    printList(newHead);
    return 0;
}

ListNode dummy(0); // dummy node before head

Create dummy node to handle edge cases like removing head

dummy.next = head;

Link dummy to head to start traversal

ListNode* slow = &dummy; ListNode* fast = &dummy;

Initialize two pointers at dummy

for (int i = 0; i < n; i++) { fast = fast->next; // advance fast pointer }

Move fast pointer n steps ahead to create gap

while (fast->next != nullptr) { slow = slow->next; // advance slow pointer fast = fast->next; // advance fast pointer }

Move both pointers until fast reaches end, slow points before target

slow->next = slow->next->next; // skip target node

Remove nth node from end by skipping it

return dummy.next; // return new head

Return updated list head

Output

1 -> 2 -> 3 -> 5 -> null

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Compared to two-pass approach (count length then remove), this one-pass method is more efficient and cleaner

Edge Cases

Removing head node (n equals list length)

Dummy node allows removing head without special code

DSA C++

ListNode dummy(0); // dummy node before head

Single node list, remove 1st from end

Returns empty list (null) correctly

DSA C++

slow->next = slow->next->next; // skip target node

n is 1 (remove last node)

Correctly removes last node by skipping it

DSA C++

while (fast->next != nullptr) { ... }

When to Use This Pattern

When asked to remove a node from the end of a linked list in one pass, use two pointers spaced n apart to find the target efficiently.

Common Mistakes

Mistake: Not using a dummy node and failing when removing the head node
Fix: Add a dummy node before head to simplify edge cases

Mistake: Moving fast pointer n+1 steps instead of n, causing null pointer errors
Fix: Move fast pointer exactly n steps ahead before moving both pointers

Mistake: Not checking fast->next in the while loop condition, causing null dereference
Fix: Use while (fast->next != nullptr) to stop before end

Summary

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

Use when you need efficient removal from the end without counting list length first.

The key insight is using two pointers spaced n nodes apart so the slow pointer lands just before the target node.

Practice

1. What does the problem "Remove Nth Node from End of List" ask you to do with a linked list?

easy

A. Add a new node at the Nth position from the end

B. Remove the node that is Nth from the start of the list

C. Reverse the linked list

D. Remove the node that is Nth from the end of the list

Solution

1. Step 1: Understand the problem statement

   The problem asks to remove the node that is Nth from the end of the linked list, not from the start or to reverse or add nodes.

2. Step 2: Clarify the operation on the list

   Removing the Nth node from the end means counting nodes from the tail backwards and deleting that node.

3. Final Answer:

   Remove the node that is Nth from the end of the list -> Option D

4. Quick Check:

   Remove Nth from end = Remove Nth from end [OK]

Hint: Focus on counting nodes from the list's end, not start [OK]

Common Mistakes:

• Confusing Nth from end with Nth from start
• Thinking the problem asks to reverse the list
• Trying to add nodes instead of removing

2. Which of the following C++ function signatures correctly represents a function to remove the Nth node from the end of a singly linked list?

easy

A. ListNode* removeNthFromEnd(ListNode* head, int n);

B. void removeNthFromEnd(int n, ListNode* head);

C. ListNode removeNthFromEnd(ListNode head, int n);

D. ListNode* removeNthFromEnd(int n);

Solution

1. Step 1: Check parameter order and types

   The function should take the head pointer of the list and the integer n as parameters, with head first and n second.

2. Step 2: Check return type

   Since the head might change (if first node is removed), the function returns a pointer to the new head.

3. Final Answer:

   ListNode* removeNthFromEnd(ListNode* head, int n); -> Option A

4. Quick Check:

   Correct signature = ListNode* removeNthFromEnd(ListNode* head, int n); [OK]

Hint: Function returns new head pointer and takes head, n as parameters [OK]

Common Mistakes:

• Wrong parameter order
• Returning ListNode instead of pointer
• Missing head parameter

3. What will be the output linked list after removing the 2nd node from the end in the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

A. 1 -> 2 -> 3 -> 5 -> null

B. 2 -> 3 -> 4 -> 5 -> null

C. 1 -> 3 -> 4 -> 5 -> null

D. 1 -> 2 -> 4 -> 5 -> null

Solution

1. Step 1: Identify the 2nd node from the end

   Counting from the end: 5 (1st), 4 (2nd). So node with value 4 is to be removed.

2. Step 2: Remove node 4 and link previous node to next

   Node 3's next pointer now points to node 5, skipping node 4.

3. Final Answer:

   1 -> 2 -> 3 -> 5 -> null -> Option A

4. Quick Check:

   Remove 2nd from end = Remove node 4 [OK]

Hint: Count nodes from end to find which to remove [OK]

Common Mistakes:

• Removing wrong node counting from start
• Not updating links correctly
• Confusing 2nd from end with 2nd from start

4. Given the following code snippet to remove the Nth node from the end, what is the bug?

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    ListNode* slow = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    while (fast->next != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return head;
}

medium

A. Uses wrong loop condition in for loop

B. Does not handle case when n equals list length (removing head)

C. Returns wrong pointer type

D. Does not move slow pointer at all

Solution

1. Step 1: Analyze fast pointer movement

   Fast pointer moves n steps ahead. If n equals list length, fast becomes nullptr.

2. Step 2: Check while loop condition

   While loop uses fast->next, but if fast is nullptr, accessing fast->next causes error. Also, removing head node is not handled.

3. Final Answer:

   Does not handle case when n equals list length (removing head) -> Option B

4. Quick Check:

   Edge case for head removal missing [OK]

Hint: Check edge cases when fast pointer reaches null early [OK]

Common Mistakes:

• Ignoring removal of head node
• Accessing fast->next without null check
• Not updating head pointer when needed

5. You want to remove the 3rd node from the end of a linked list with nodes: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null. Which of the following steps correctly describes the process using two pointers?

hard

A. Move slow pointer 3 steps ahead, then move fast pointer until slow reaches end, then remove fast's next node.

B. Move fast pointer 3 steps ahead, then move slow pointer 3 steps ahead, then remove head node.

C. Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node.

D. Move both pointers together from start without offset, then remove the node at position 3.

Solution

1. Step 1: Initialize two pointers at head

   Start both fast and slow pointers at the head of the list.

2. Step 2: Move fast pointer n steps ahead

   Move fast pointer 3 steps ahead to create a gap of 3 nodes between fast and slow.

3. Step 3: Move both pointers until fast reaches end

   Move fast and slow pointers one step at a time until fast reaches the last node.

4. Step 4: Remove the node after slow pointer

   Slow pointer now points to node before the target; remove slow->next node.

5. Final Answer:

   Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node. -> Option C

6. Quick Check:

   Two-pointer gap method = Move fast pointer 3 steps ahead, then move both pointers until fast reaches end, then remove slow's next node. [OK]

Hint: Use two pointers with gap n to find node before target [OK]

Common Mistakes:

• Moving slow pointer first instead of fast
• Removing wrong node after pointers move
• Not creating correct gap between pointers