Wednesday, 22 February 2017

C++ Program to find the Nth node of the Linked List from the End

This question has already appeared in the interveiws of the following questions
Epic Systems, Snapdeal, Monotype Solutions, Adobe, Amazon, Citicorp

Source:- geeksforgeeks

we strongly recommend you to first try this question yourself at geeksforgeeks before seeing the editorial. 


 In the question, you have given a linked list and you have to complete a given method which is taking two arguments head node of the linked list and the n (the node which you have to find) and you have to return the value of that nth node.


The completed function is given below:



/* struct Node
 {
   int data;
   Node* next;
 }; */

/* Should return data of n'th node from the end of linked list */
int getNthFromLast(Node *head, int n)
{
       struct Node *current;
       current=head;
       int count=0;
       while(current!=NULL)
       {
            count++;
            current=current->next;
       }
       if(count<n)
       {
              return -1;
       }
       if(count==n)
       {
           return head->data;
       }
       else
       {
              current=head;
              while(current!=NULL)
              {
                    if(count==n+1)
                    {
                           current=current->next;
                           return current->data;
                    }
                    else
                    {
                        count--;
                        current=current->next;
                    }
              }
       }
      
}

Complete program for finding the nth node from end of the linked list is also given below in  the case you want to understand and try the complete program.


#include <stdio.h>
#include <stdlib.h>
struct node
{
   int data;
   struct node *next;
};

class linklist{
 
   private:
         int data;
         node *head,*current;
   public:
         void get_data();
         int find_node(int n);
         void print();
};
void linklist::get_data()
{
 
      head=NULL;
      current=(struct node*)malloc(sizeof(struct node));
      current->data=8;
      current->next=NULL;
      if(head==NULL)
      {
             head=current;
      }
      current->next=(struct node*)malloc(sizeof(struct node));
      current=current->next;
      current->data=16;
      current->next=(struct node*)malloc(sizeof(struct node));
      current=current->next;
      current->data=25;
      current->next=(struct node*)malloc(sizeof(struct node));
      current=current->next;
      current->data=45;
      current->next=(struct node*)malloc(sizeof(struct node));
      current=current->next;
      current->data=50;
      current->next=NULL;

}
void linklist::print()
{
   current=head;
   while(current!=NULL)
   {
           printf("%d->",current->data);
           current=current->next;
   }
   int n;
   printf("\nEnter the nth node from the end which you want to found: ");
   scanf("%d",&n);
   printf("\n\nThe nth node is: %d",find_node(n));
}
int linklist::find_node(int n)
{
 
       current=head;
       int count=0;
       while(current!=NULL)
       {
            count++;
            current=current->next;
       }
       if(count<n)
       {
              return -1;
       }
       if(count==n)
       {
           return head->data;
       }
       else
       {
              current=head;
              while(current!=NULL)
              {
                    if(count==n+1)
                    {
                           current=current->next;
                           return current->data;
                    }
                    else
                    {
                        count--;
                        current=current->next;
                    }
              }
       }
      
}
int main()
{
   linklist ll;
   ll.get_data();
   ll.print();
   return 0;
}


OUTPUT:

 


EmoticonEmoticon