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.
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.
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