C++ Linked List Exercises: Delete the n^th node of a Singly Linked List from end

C++ Linked List: Exercise-13 with Solution

Write a C++ program to delete the n^th node of a Singly Linked List from the end.

Test Data:
Original list:
7 5 3 1
Remove the 2nd node from the end of the said list:
Updated list:
7 5 1
Remove the 3rd node from the end of the said list:
Updated list:
5 1

Sample Solution:

C++ Code:

  #include <iostream> // Including input-output stream header file

using namespace std; // Using standard namespace

struct Node // Declare a structure for defining a Node
{   
    int num; // Data field to store a number
    Node *next; // Pointer to the next node
}; // Node constructed

int sizen = 0; // Initializing variable to keep track of the size of the linked list

// Function to insert a node at the start of the linked list
void insert(Node** head, int num){
    Node* new_Node = new Node(); // Creating a new node
    new_Node->num = num; // Assigning data to the new node
    new_Node->next = *head; // Pointing the new node to the current head
    *head = new_Node; // Making the new node as the head
    sizen++; // Increasing the size of the linked list
}

// Function to delete the nth node from the end of the linked list
Node* delete_last_node(Node* head, int n) {
    Node *p = head, *q = head; // Initializing pointers p and q to head node
    while (n--) q = q->next; // Moving q 'n' nodes ahead from head
    if (!q) return head->next; // If q reaches the end, remove the first node
    while (q->next) { // Until q reaches the end
        p = p->next; // Move p forward
        q = q->next; // Move q forward
    }
    Node* toDelete = p->next; // Node to be deleted
    p->next = p->next->next; // Deleting the node
    delete toDelete; // Freeing the memory of the deleted node
    return head; // Returning the head of the updated list
}

// Function to display all nodes in the linked list
void display_all_nodes(Node* node)
{ 
    while(node != NULL){ // Loop through all nodes until the end is reached
        cout << node->num << " "; // Displaying the data in the current node
        node = node->next; // Move to the next node
    } 
}

int main()
{
    Node* head = NULL; // Initializing the head of the linked list as NULL

    insert(&head,1); // Inserting a node with value 1
    insert(&head,3); // Inserting a node with value 3
    insert(&head,5); // Inserting a node with value 5
    insert(&head,7); // Inserting a node with value 7

    cout << "Original list:\n"; // Displaying message for the original list
    display_all_nodes(head); // Displaying all nodes in the original list

    int pos = 2; // Position of the node to be removed from the end
    cout << "\n\nRemove the " << pos << "nd node from the end of the said list:";
    cout << "\nUpdated list:\n";
    head = delete_last_node(head, pos); // Removing the node from the end
    display_all_nodes(head); // Displaying all nodes after removal

    pos = 3; // Position of the node to be removed from the end
    cout << "\n\nRemove the " << pos << "rd node from the end of the said list:";
    cout << "\nUpdated list:\n";
    head = delete_last_node(head, pos); // Removing the node from the end
    display_all_nodes(head); // Displaying all nodes after removal

    cout << endl; // Displaying newline
    return 0; // Returning from the main function
}

Sample Output:

Original list:
7 5 3 1

Remove the 2nd node from the end of the said list:
Updated list:
7 5 1

Remove the 3rd node from the end of the said list:
Updated list:
5 1

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Delete the last node of a Singly Linked List.
Next C++ Exercise: K^th node from the Middle towards Head of a Linked List.