nth node from end of Linked List

Today we will discuss how to find nth node from end of linked list. But, if you don't know what linked lists are then please refer to this post where I have explained everything about linked list. Let me explain you about the problem. Suppose we have a linked list 1->2->3->4->5 and we are asked to find 2th node from end, then the answer 2nd node from end would be 4. Now let's understand how to solve nth node from end of linked list problem.

Procedure

1. First we will make a linked list.
2. Then we will count number of nodes in the linked list.
3. Then we the following formulae to find the position of nth node from beginning.
Suppose the list is 1->2->3->4->5 and we have to find 2nd node from end. Then we can also say that we have to find the 4th node from beginning because 2nd node from end and 4th node from the beginning are the same. Now there's a formula you can use to find position of a node from beginning when its position is given from the end:-

 position of node from beginning = number of nodes - position of node from end +1

4. Now that we have got the position of node from beginning so we can simply iterate till that position and print the output.

Code

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL; class linked { public: void insert(int x) { struct node* temp=new node(); temp->data=x; temp->next=NULL; if(head==NULL) { head=temp; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp1->next =temp; } } void nthnodefromend(int x) { struct node* temp=head; int c=0; while(temp!=NULL) { temp=temp->next; c++; } c=c-x; temp=head; int t=1; while(t<=c) { temp=temp->next; t++; } cout<<x<<"th node from end is "<<temp->data<<endl; } void disp() { struct node* temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } }; int main() { linked l; l.insert(2); l.insert(5); l.insert(21); l.insert(46); l.insert(48); l.insert(54); l.insert(10); l.disp(); int n; cout<<"enter position of node from end to be searched: "; cin>>n; l.nthnodefromend(n); return 0; }

Explanation of code(line by line)

1. First we will write a simple code of linked list which will have 2 functions:

     - insert() - which will insert elements in the linked list.
     - disp() - which will display the linked list.

2. Insert some values in the linked list.
3. Now we have created a function named nthnodefromend() to find nth node from end of a linked list. This function takes an argument 'x' which denotes the position of node we have to find from the end.
4. First we have created a pointer to node temp which is initialized with head and a variable 'c' which is initialized to 0. 'c' will store the number of nodes in the list.
    struct node* temp=head;
    int c=0;
5. Then we have started a while loop to count number of nodes in the list.
    while(temp!=NULL)
   {
        temp=temp->next;
        c++;
   }
6. Then we have used the formula to find position of a node from beginning when the position from end is given:

   position of node from beginning = number of nodes - position of node from end +1

c=c-x;

7. We have not added 1 to the above statement because a linked list starts its traversal from the first node itself.

8. Then we have initialized temp to head again and we have made another variable named t initialized to 1 which will be a counter variable which will iterate list till desired position.

     temp=head;
     int t=1;

9. Then we have started a while loop which will iterate till the position of node from beginning. That means list will iterate from t=1 to c as we have stored the position of node from beginning in c itself.

    while(t<=c)
   {
      temp=temp->next;
      t++;
   }

10.At last we have printed the data in the node which was xth from then end of the list.