Remove Nth Node from End of List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after removing 2nd node from end

What is the output linked list after removing the 2nd node from the end in the given list?

DSA C++

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

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

// Initial list: 1 -> 2 -> 3 -> 4 -> 5 -> null
// Remove 2nd node from end (node with value 4)
// Print resulting list

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

B 1 -> 2 -> 3 -> 4 -> null

C 1 -> 2 -> 4 -> 5 -> null

D 2 -> 3 -> 4 -> 5 -> null

💡 Hint

Use two pointers with a gap of n nodes to find the node before the one to remove.

The function moves the fast pointer n steps ahead, then moves both pointers until fast reaches the end. The slow pointer then points to the node before the one to remove. Removing the 2nd node from the end removes the node with value 4.

❓ Predict Output

intermediate

Output after removing 1st node from end

What is the output linked list after removing the last node (1st from end) in the given list?

DSA C++

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

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

// Initial list: 1 -> 2 -> 3 -> 4 -> 5 -> null
// Remove 1st node from end (node with value 5)
// Print resulting list

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

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

C 2 -> 3 -> 4 -> 5 -> null

D 1 -> 2 -> 3 -> 4 -> null

💡 Hint

Removing the last node means the second last node's next becomes null.

The last node (value 5) is removed, so the list ends at node with value 4.

🔧 Debug

advanced

Identify the error in this Remove Nth Node code

What error will this code produce when removing the 3rd node from end in a 3-node list?

DSA C++

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

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

// List: 1 -> 2 -> 3 -> null
// Remove 3rd node from end (node with value 1)

A No error, output: 2 -> 3 -> null

B Runtime error: null pointer dereference

C Compilation error: missing semicolon

D Logic error: removes wrong node

💡 Hint

Check the for loop condition and how many times fast moves.

The for loop moves fast pointer n+1 times, which causes fast to become null or invalid when n equals list length, leading to null pointer dereference in the while loop.

🧠 Conceptual

advanced

Why use two pointers in Remove Nth Node from End?

Why does the two-pointer technique work for removing the nth node from the end of a linked list?

A Because moving one pointer n steps ahead creates a gap to find the node before the target in one pass

B Because two pointers can traverse the list twice as fast

C Because one pointer can reverse the list while the other deletes nodes

D Because two pointers avoid using extra memory for storing nodes

💡 Hint

Think about how the gap helps locate the node to remove.

Moving one pointer n steps ahead creates a fixed gap so when the fast pointer reaches the end, the slow pointer is just before the node to remove, enabling removal in one pass.

❓ Predict Output

expert

Output after removing 5th node from end in single-node list

What happens when you try to remove the 5th node from the end in a list with only one node?

DSA C++

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    ListNode* slow = head;
    for (int i = 0; i < n; ++i) {
        if (!fast) return head; // n is larger than list length
        fast = fast->next;
    }
    if (!fast) {
        ListNode* newHead = head->next;
        delete head;
        return newHead;
    }
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete;
    return head;
}

// List: 1 -> null
// Remove 5th node from end

A Runtime error: null pointer dereference

B null

C 1 -> null

D Compilation error

💡 Hint

Check how the code handles n larger than list length.

The code checks if fast becomes null before moving n steps, returning the original list unchanged if n is too large.

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