Find nth Node from End of Linked List – C++

In this article, we discuss a method and a program to find the nth node from the end of a linked list in C++. We know that a singly-linked list is a data structure that is linear and uni-directional. This property of linked lists prevents us from directly locating the nth node from the end.

Find the nth Node from End of Linked List – C++

We should, therefore, find a way to locate the required node from the beginning of the list. For this, we find out the total number of nodes ( say, ‘num’ ). Then locating the ( num – i )th node from the beginning.

To find the total number of nodes we first run a loop from the first node till the last.  This can be done by checking for the pointer from the start to the one that points to NULL. i.e. the loop exits when the pointer points to NULL.

Now, have a look at the code.

 

Code

#include<iostream>

using namespace std;

int counter = 0;

/* Counter will hold the value of the total number of nodes */
struct node
{
    int number;
    node *next;
};

node *start = NULL, *temp = NULL;

node *create(int num)
{
    node *newnode = new node;

    newnode -> number = num;
    newnode -> next = NULL;

    return newnode;
}

void insertNode(int value)
{

    if(start == NULL)
    {
        start = temp = create(value);
    }

    else
    {
        temp -> next = create(value);
        temp = temp -> next;
    }

}

void display()
{

    node *temp = start;

    while(temp != NULL)
    {
        cout<<temp -> number<<" -> ";
        temp = temp -> next;
    }

    cout<<" NULL";

}

int main()
{

    int num;
    int index;
    char ch;

    do
    {
        cout<<"ENTER NUMBER : ";
        cin>>num;

        insertNode(num);
        counter++;

        cout<<"DO YOU WANT TO CONTINUE ?";
        cin>>ch;

    }while(ch == 'y' || ch == 'Y');

    display();

    cout<<"\n\nTOTAL NUMBER OF NODES : "<<counter;

    cout<<"ENTER THE INDEX OF REQUIRED NODE FROM END : ";
    cin>>index;

    temp = start;

    for(int i=0; i<counter - index; i++)
    {
        temp = temp -> next;
    }

    cout<<"\n\nREQUIRED NODE : "<<temp -> number;

    return 0;
}

 

Output

ENTER NUMBER : 1
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 2
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 3
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 4
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 5
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 6
DO YOU WANT TO CONTINUE ?n
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

TOTAL NUMBER OF NODES : 6
ENTER THE INDEX OF REQUIRED NODE FROM END : 3


REQUIRED NODE : 4

 

Analysis

Let us analyze the code we just skimmed through. You can neglect this section if you are comfortable with insertion and traversal through linked lists. The indexing starts from ‘1’, for the user-input position index.

 

First, we insert the nodes into a linked list. For this, we have a structure named node. We create a new node in the create( arguments ) function and return the newly created node to a pointer which points to the same. The ‘start’ pointer, as the name suggests, points to the beginning of the linked list. The ‘temp’ pointer is used as a traversing pointer.

 

The insert function sets the user-input as the node’s data-part and the next-part pointing to NULL. We increment a counter so that we get the total number of nodes inserted. Once the insertion is completed, we run another loop, this time till (total_number_of_nodes – required_index) number of times, since now we have the value of the total number of nodes. By this, we can locate the required node with an index from the end of the list.

 

Feel free t0 read the following articles :

 

Leave a Reply

Your email address will not be published. Required fields are marked *