Problem Statement

Given a linked list, remove the N-th node from the end of the list and return its head

Examples

Example 1:

Input: List = [5, 1, 2, 3], N = 2
Output: List = [5, 1, 3]

Explanation: The 2nd node from the end of the linked list is 2. Therefore, we get this result after removing 2 from the linked list.

Example 2:

Input: List = 5->4->3->2->1, N = 5
Output: List = 4->3->2->1

Explanation: The 5th node from the back is the first node.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

1. Calculation of Length:
   1. First, we find the total length of the linked list by traversing it once. This helps us determine the position of the node we want to delete.
2. Deletion of Node:
   1. Next, we locate and delete the node that is (length - N + 1) nodes from the start of the list. This effectively removes the N-th node from the end.
3. Edge Cases:
   1. If N equals 1, we delete the tail of the linked list.
   2. If N equals the length of the linked list, we delete the head of the linked list.

Algorithm:

1. Initialize a temp pointer that will be used to traverse the list.
2. Create a count variable and initialize it to 0. Traverse the linked list, and each node, increment count. Finally, when the pointer reaches nullptr, return count, which contains the total length of the linked list.
3. Now, after knowing the length, we need to delete (L - N + 1), create a new temp pointer to the head. Initialize a variable res to L - N, and start iterating the linked list while decrementing result at each node. Once result equals 0, we know that temp will be pointing to the L - N th node, therefore stop the traversal.
4. To create a new link, point the (L-N)th node to the (L-N+2)th node of the linked list, effectively skipping the (L-N+1)th node.
5. Finally, free up the memory being occupied by the (L-N+1)th node, thus deleting this node.

Code:

class Node {
public:
    int data;
    Node* next;

    // Constructor for Node with data and next node
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor for Node with 
    //only data (next set to nullptr)
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to print the linked list
void printLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

// Function to delete the Nth node
// from the end of the linked list
Node* DeleteNthNodefromEnd(Node* head, int N) {
    if (head == NULL) {
        return NULL;
    }
    int cnt = 0;
    Node* temp = head;

    // Count the number of nodes in the linked list
    while (temp != NULL) {
        cnt++;
        temp = temp->next;
    }

    // If N equals the total number of
    // nodes, delete the head
    if (cnt == N) {
        Node* newhead = head->next;
        delete (head);
        return newhead;
    }

    // Calculate the position of the node to delete (res)
    int res = cnt - N;
    temp = head;

    // Traverse to the node just before the one to delete
    while (temp != NULL) {
        res--;
        if (res == 0) {
            break;
        }
        temp = temp->next;
    }

    // Delete the Nth node from the end
    Node* delNode = temp->next;
    temp->next = temp->next->next;
    delete (delNode);
    return head;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int N = 3;
    Node* head = new Node(arr[0]);
    head->next = new Node(arr[1]);
    head->next->next = new Node(arr[2]);
    head->next->next->next = new Node(arr[3]);
    head->next->next->next->next = new Node(arr[4]);

    // Delete the Nth node from the end
    // and print the modified linked list
    head = DeleteNthNodefromEnd(head, N);
    printLL(head);
}

Complexity Analysis:

Time Complexity: O(L) + O(L-N)

• We are calculating the length of the linked list and then iterating up to the (L - N) th node of the linked list, where L is the total length of the list.

Space Complexity: O(1)

• As we are not using any extra space.

2️⃣ Optimal Approach

The brute force, in the worst case, has a time complexity of O(2*L), where L is the length of the linked list. Therefore, it is not the most efficient algorithm, as we are traversing the entire list twice.

To improve efficiency, we will use two pointers: a fast pointer and a slow pointer. Initially, the fast pointer will be N nodes ahead of the slow pointer. As both pointers move forward, when the fast pointer reaches the end of the list, the slow pointer will be exactly (L-N) nodes from the end, where L is the length of the linked list.

Visualization:

A -> B -> C -> D -> E -> F -> nullptr, n = 2

Initialization:

A (lead | lag) -> B -> C -> D -> E -> F -> nullptr

Advance Lead Pointer by n = 2:

A (lag) -> B -> C (lead) -> D -> E -> F -> nullptr

First Iteration to advance lead and lag by 1:

A -> B (lag) -> C -> D (lead) -> E -> F -> nullptr

Second Iteration to advance lead and lag by 1:

A -> B -> C (lag) -> D -> E (lead) -> F -> nullptr

Third Iteration to advance lead and lag by 1:

A -> B -> C -> D (lag) -> E -> F (lead) -> nullptr

Now, lead->next is nullptr so, break the loop
and lag->next == required nth node from the end,
just remove it.

Algorithm:

1. Initialization of Pointers:
   1. Start with two pointers, slow and fast, both set to the head of the linked list. Initially, only the fast pointer will move until it crosses N nodes.
2. Traverse the List:
   1. Move both pointers simultaneously. The fast pointer moves ahead until it reaches the last node (Lth node), while the slow pointer lags N nodes behind.
3. Locating the Target Node:
   1. At this stage, the slow pointer is precisely at the (L-N)th node from the beginning of the list. This node is the one preceding the node to be deleted.
4. Skipping the Target Node:
   1. Adjust the slow pointer to skip the Nth node from the end. Point it to the node after the one to be deleted, effectively removing the Nth node from the end or the (L-N+1)th node from the start.
5. Memory Deallocation:
   1. Free up the memory occupied by the node to be deleted.

Code:

#include<bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    // Constructor
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor 
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to print the linked list
void printLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

// Function to delete the Nth node
// from the end of the linked list
Node* DeleteNthNodefromEnd(Node* head, int N) {
    // Create two pointers, fastp and slowp
    Node* fastp = head;
    Node* slowp = head;

    // Move the fastp pointer N nodes ahead
    for (int i = 0; i < N; i++)
        fastp = fastp->next;

    // If fastp becomes NULL,
    // the Nth node from the end is the head
    if (fastp == NULL)
        return head->next;

    // Move both pointers until fastp reaches the end
    while (fastp->next != NULL) {
        fastp = fastp->next;
        slowp = slowp->next;
    }

    // Delete the Nth node from the end
    Node* delNode = slowp->next;
    slowp->next = slowp->next->next;
    delete delNode;
    return head;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int N = 2;
    Node* head = new Node(arr[0]);
    head->next = new Node(arr[1]);
    head->next->next = new Node(arr[2]);
    head->next->next->next = new Node(arr[3]);
    head->next->next->next->next = new Node(arr[4]);

    // Delete the Nth node from the end 
    // and print the modified linked list
    head = DeleteNthNodefromEnd(head, N);
    printLL(head);
}

// Output
1 2 3 5

Complexity Analysis:

• Time Complexity: O(N)
  • Since the fast pointer will traverse the entire linked list, where N is the length of the linked list.
• Space Complexity: O(1)
  • As we have not used any extra space.