Remove Nth Node From End of List - C++ Solution

1. Introduction

This blog post discusses a common problem in linked list manipulation: removing the nth node from the end of the list. This problem tests one's ability to traverse and modify linked lists efficiently.

Problem

Given the head of a linked list, the task is to remove the nth node from the end of the list and return the updated head of the list.

2. Solution Steps

1. Use two pointers: fast and slow. Initially, both point to the head.

2. Advance the fast pointer n steps ahead.

3. Move both fast and slow until fast reaches the end of the list. Now, slow will be right before the node to be deleted.

4. Remove the nth node by changing the next pointer of the slow node.

5. Handle edge cases, such as when the removed node is the head of the list.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to remove the nth node from the end of the list
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *fast = &dummy, *slow = &dummy;

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

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

    // Remove the nth node
    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete;

    return dummy.next;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    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);

    int n = 2;
    head = removeNthFromEnd(head, n);
    printLinkedList(head); // Expected output: 1 -> 2 -> 3 -> 5 -> nullptr
    return 0;
}

Output:

1 -> 2 -> 3 -> 5 -> nullptr

Explanation:

The removeNthFromEnd function uses a two-pointer approach to find and remove the nth node from the end of the list. 

A dummy node is used to simplify edge cases, especially when the removed node is the head. 

The fast pointer is first moved n steps ahead, and then both fast and slow pointers are moved until fast reaches the end. 

This positions slow right before the node is removed. The node is then removed by updating the next pointer of the slow node. 

The function returns the head of the modified list, with the nth node from the end removed.