Saturday, 21 June 2014

Find nth Element from last in a Single Linked List

We have to find nth element from last in a given linked list. Below is the algorithm used for the same
  • Take 2 pointers both pointing to head of linked list.
  • Move the first pointer to next element n number of times.
  • Now Start moving the second pointer till first pointer reaches end of linked list.
  • The data in the node of second pointer is your nth element from last.
See  FindFromLast function for implementation of algorithm.


Input:     number of elements in Linked List
              values in number of elements
              n
Output : nth element from last

For Example:

Input:    7
             3 9 4 13 11 7 2
             4

Output  13



#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
Node * Insert ( Node *head ,int data )
{
    if ( head==NULL )
    {
        head=new Node;
        head->data=data;
        head->next=NULL;
        return head;


    }

    else
    {
        Node *q=NULL;
        q=new Node;
        q->data=data;
        q->next=head;
        return q;
    }
}
int FindFromLast ( Node *head,int n )
{
    int i=n,j=1;
    Node *p=head,*q=head;
    while ( j<=n )
    {

        p=p->next;

        j++;
    }
    while ( p!=NULL )
    {
        q=q->next;
        p=p->next;
    }
    return q->data;
}
int main()
{
    Node *start=NULL;
    int n,input,data;
    cin>>input;
    for ( int i=1; i<=input; i++ )
    {
        cin>> data;
        start=Insert ( start,data );
    }
    cin>>n;
    if ( n>input ||n<=0 )
    {
        cout<<"Enter a number less than total elements and greater than zero";
    }
    else
    {
        cout<<FindFromLast ( start,n );
    }

}

Please comment if you find anything incorrect or have any other inputs.

No comments:

Post a Comment