Remove Nth Node from End of List in DSA C++ - Build from Scratch

Remove Nth Node from End of List

📖 Scenario: You are working on a simple contact list app. The contacts are stored in a singly linked list, where each node contains a contact's name. Sometimes, you need to remove a contact from the list counting from the end, for example, remove the 2nd last contact.

🎯 Goal: Build a program that creates a singly linked list of contacts, then removes the nth node from the end of the list, and finally prints the updated list.

📋 What You'll Learn

Create a singly linked list with exactly these contacts in order: "Alice", "Bob", "Charlie", "David", "Eve"

Create an integer variable n with the value 2

Implement a function removeNthFromEnd that removes the nth node from the end of the list

Print the updated linked list after removal in the format: Name1 -> Name2 -> ... -> null

💡 Why This Matters

🌍 Real World

Linked lists are used in many applications like contact lists, music playlists, and undo functionality where dynamic insertion and deletion are needed.

💼 Career

Understanding linked list manipulation is important for software engineering roles, especially those involving low-level data structures, memory management, or coding interviews.

1

Create the linked list with contacts

Create a singly linked list with nodes containing these exact contact names in order: "Alice", "Bob", "Charlie", "David", "Eve". Use the struct ListNode with a string val and ListNode* next. Create a pointer head pointing to the first node.

DSA C++

#include 
#include 
using namespace std;

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

int main() {

    // Create linked list nodes and link them
    // Your code here

    return 0;
}

Hint

Start by creating the first node with "Alice" and assign it to head. Then link each next node using head->next, head->next->next, and so on.

2

Create the variable for position from end

Create an integer variable called n and set it to 2. This will represent the position from the end of the list of the node to remove.

DSA C++

#include 
#include 
using namespace std;

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

int main() {
    ListNode* head = new ListNode("Alice");
    head->next = new ListNode("Bob");
    head->next->next = new ListNode("Charlie");
    head->next->next->next = new ListNode("David");
    head->next->next->next->next = new ListNode("Eve");

    // Create variable n
    // Your code here

    return 0;
}

Hint

Just write int n = 2; below the linked list creation.

3

Implement the function to remove nth node from end

Write a function called removeNthFromEnd that takes ListNode* head and int n as parameters and returns the head of the updated list after removing the nth node from the end. Use two pointers to find the node to remove. Then call this function inside main to update head.

DSA C++

#include 
#include 
using namespace std;

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // Implement two pointer approach to remove nth node from end
    // Your code here
}

int main() {
    ListNode* head = new ListNode("Alice");
    head->next = new ListNode("Bob");
    head->next->next = new ListNode("Charlie");
    head->next->next->next = new ListNode("David");
    head->next->next->next->next = new ListNode("Eve");

    int n = 2;

    head = removeNthFromEnd(head, n);

    return 0;
}

Hint

Use a dummy node before head. Move first pointer n+1 steps ahead, then move both first and second until first reaches end. Remove the node after second.

4

Print the updated linked list

Write a while loop to print the updated linked list starting from head. Print each node's val followed by " -> ". After the last node, print "null".

DSA C++

#include 
#include 
using namespace std;

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode("");
    dummy->next = head;
    ListNode* first = dummy;
    ListNode* second = dummy;

    for (int i = 0; i next;
    }

    while (first != nullptr) {
        first = first->next;
        second = second->next;
    }

    ListNode* toDelete = second->next;
    second->next = second->next->next;
    delete toDelete;

    ListNode* newHead = dummy->next;
    delete dummy;
    return newHead;
}

int main() {
    ListNode* head = new ListNode("Alice");
    head->next = new ListNode("Bob");
    head->next->next = new ListNode("Charlie");
    head->next->next->next = new ListNode("David");
    head->next->next->next->next = new ListNode("Eve");

    int n = 2;

    head = removeNthFromEnd(head, n);

    // Print the updated list
    // Your code here

    return 0;
}

Hint

Use a while loop to go through each node starting from head. Print the val followed by " -> ". After the loop, print "null".

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