Interview Questions And Answers 
-
Write a function to find the nth item from the end of a linked list in a single pass.
7,859 Views |
(27 votes, avg: 3.15)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Write a function to find the nth item from the end of a linked list in a single pass.
7,859 Views | (27 votes, avg: 3.15)
Loading ...
1) have two ptrs. F_Ptr & S_Ptr.
2) Let the ptrs point to the START.
3) Take n as the offset.
4) Start traversing the S_Ptr after the F_Ptr after n.
suppose u want to find 5 element from the last of the list.
In the above case.
1) n = 5 // 5th element from the last
2) check atleast this many elements are there in the list before beginging
// traverse the F_Ptr offset
for(;n!=0;n–,F_Ptr->next);
// now set the S_Ptr to trail the F_Ptr
S_Ptr = F_Ptr;
for(;F_Ptr!=NULL; S_Ptr=F_Ptr; F_Ptr=F_Ptr->next)
Now whe F_Ptr = Null, S_Ptr is just trailing behind right! it will be pointing to the n’th element from the last.
When F_Ptr reaches end (i.e., F_Ptr is NULL)
S_Ptr points to the 5th element from the last.
The Solution with two pointers is a good one.You can also do this recursively. The code for that goes below.I might be missing some extensive checking but it works fine in this scenario. The boundary case cheking are not checked. you will get an exception if you will pass the number greater than the list length and some other things like that. I hope this will help.
class node{
public:
int data;
node* next;
};
#include “node.h”
#include<iostream.h>
class mylist{
private:
node* first;
public:
mylist(){
first=NULL;
}
void addItem(int d);
void getNthElement(node* temp,node*& temp1,int &n,int &count);
node* getNthElement(int n);
void show();
};
node* mylist::getNthElement(int n){
node* temp1;
int count=0;
getNthElement(first,temp1,n,count);
cout<<temp1->data<<endl;
return temp1;
}
void mylist::show(){
node* temp = first;
while(temp!=NULL){
cout<<temp->data<<endl;
temp=temp->next;
}
}
void mylist::addItem(int d){
node* newNode = new node();
newNode->data = d;
newNode->next = first;
first = newNode;
}
void mylist::getNthElement(node* temp,node*& temp1,int &n,int &count){
if(temp==NULL){
count++;
return;
}
getNthElement(temp->next,temp1,n,count);
if(count==n){
temp1=temp;
count++;
return;
}else{
count++;
return;
}
}
void main(){
mylist l;
node* temp1;
l.addItem(3);
l.addItem(5);
l.addItem(6);
l.addItem(7);
//l.show();
l.getNthElement(2);
}
Why are u setting sptr to fptr.
My guess will be
To find nth element from the end u should advance fptr n number of times whereas sptr stays at the beginning.After that do
fptr = fptr->next;
sptr = sptr->next;
when fptr is NULL then sptr will be at the nth element from end as we have already moved fptr by n number of times.
Please correct and explain if I am wrong
I would think keeping a gap os “n” between fptr and sptr would do.
then advance both together till fptr->next (fptr is the one in front) = NULL
Dudes,
Arent you traversing the list twice - once with fptr and the second time with sptr.
I think you should maintain an queue of pointers. Keep pushing the pointer into the queue and whenever the size of the queue becomes greater than n, remove the pointer at the head of the queue. When you reach the end of the list.. the element at the head of the queue gives a pointer to the nth element from the finish.
Vijay
with a queue, you risk up to O(n) space complexity - for example, if your list is 100 elements long, and you want the 100th element from the end of the list. With no more than two pointers, your space complexity will be O(1).
In addition, your queue operations will tend to be much slower than advancing the ‘caboose’ pointer. Calling “caboose = caboose->next” certainly has less overhead than calling a Pop operation followed by a Push operation for every step in the list.
Thus, your queue will achieve the worst of both worlds.
#include
#include
typedef struct node
{
int info;
struct node *next;
}node;
void nthnode(node **,int);
void make(node **,int);
void display(node *);
void main()
{
node *p;
int i,x,n;
p=NULL;
for(i=0;iinfo);
t=t->next;
}
}
void make(node **t,int x)
{
node *temp;
temp=(node *)malloc(sizeof(node));
temp->info=x;
temp->next=*t;
*t=temp;
}
void nthnode(node **t,int n)
{
node *fptr,*sptr;
int count=0;
fptr=sptr=*t;
while(sptr!=NULL)
{
if(countnext;
count++;
}
else
{
sptr=sptr->next;
fptr=fptr->next;
}
}
printf(”%d”,fptr->info);
}
for eg..
if we enter
1
2
3
4
5
6
7
8
9
then link list is
9 8 7 6 5 4 3 2 1 (since we r adding nodes from the beginning)
enter n : 6
ans=6
How about reversing the list first?
Actually, you can use a stack.
Iam not sure whether this is right…….
1.top = -1
2.push the nodes of the LL starting from the head into a stack(temp = head; head = head->next;push temp; top++;temp = head)
3. simultaneously increment the top pointer.
4. get the n value (spse n=3)
5. pop n times (3 times) from the stack
hey guy.. many of u have commented that we are traversing
list twice, bit its not true.. jsut think we are using the value of pointer F_Ptr get through travesing.
and we are assigning it to S_Ptr when F_Ptr is leading by n.
S_Ptr (kth node) =F_Ptr((k+5)node) ;
i hope it ll clear you guys.
node* findlast(node *head,int n)
{
node *first,*last;
last = head;
first = head;
int i = 0 ;
while(first !=NULL)
{
if(i>=n)
last = last->next;
i = i + 1;
first= first->next;
}
return last;
}
Algo:
1) Traverse the LIST till the end , get the size of the list .. Say SIZE.
2) the N th element from the last wud be (SIZE - N) elements away from the Begining of the list.
node *findlast(node *head,int n)
{
node* temp1=head;
node* temp2=head;
for(int i=0;inext;
if(!temp1)
return NULL;
while(temp1)
{
temp2=temp2->next;
temp1=temp1->next;
}
return temp2;
}
node *findlast(node *head,int n)
{
node* temp1=head;
node* temp2=head;
for(int i=0;inext;
if(!temp1)
return NULL;
while(temp1)
{
temp2=temp2->next;
temp1=temp1->next;
}
return temp2;
}
Although the 2 pointer solution suffices, we have another one here, which goes as:
1. Traverse the linked list & store the pointer to every node in an array ARR.
2. When the end of the list, we have the total number of nodes M in the list. Then we can use ARR[M-n+1], where n is the desired element from last.
E.g.
List (I have taken numbers for simplicity, will work for any information structure): 1,2,3,4,5,6,7.
Say our n =3 (i.e. 3rd element from the last)
Traversing the list our array ARR has pointer to the location of every element as per their position in the list.
ARR = {p1,p2,p3,p4,p5,p6,p7}
Now after the traversal we now that M=7 & n=3 we have ARR[7-3+1]=ARR[5] which is the pointer to 5….
We do have to have extra space..but then the question is silent about the space usage…
class node
{
public:
node(int ii){i=ii; next=0;}
int i;
node* next;
};
int N=3;
int nVar=0;
node* nthNODE=0;
int FindNext(node *p)
{
if(p->next != 0)
{
int r=FindNext(p->next);
if(r==N)
{
nthNODE=p->next;
}
}
else
{
nVar=1;
}
return nVar++;
}
void FindNElemfromEnd()
{
node *p,*head=new node(1);
p=head;
p->next=new node(2);
p=p->next;
p->next=new node(3);
p=p->next;
p->next=new node(4);
FindNext(head);
node* nthNode=nthNODE; // nth Node from the End
}
we can use doubly link list.
transverse start from tail…….
with particular position…
(no define of using linear link list)
Leave an Answer/Comment