Amazon Interview Question Software Engineer / Developers
Team: Kindle-Periodicals
Country: India
Interview Type: In-Person
Comment hidden because of low score. Click to expand.
2
of 2 vote
Take two pointers P1 and P2 and point both of them to the root of the linked list. Move P1 to Nth Node and then start moving both P1 and P2 until P1 reaches the end of linked list. In the end, P1 would be pointing to the Nth last node.
{{{
struct Node
{
Node * next;
int val;
}
Node *root; // Assuming the linked list is already made up.
int main()
{
cout<<"Enter the value of n";
cin>>n;
Node *p1 = root, *p2 = root;
for(int i = 0; p2 != NULL; )
{
if ( i > n )
{
p1 = p1->next;
}
p2 = p2->next;
i++;
} // for
if(i<n)
cout<< "Nodes insufficient!":
else
cout<<"Nth Last Node is"<<p1->val;
} // int main()
-
cartman
March 18, 2012
Comment hidden because of low score. Click to expand.
1
of 3 vote
Take 2 pointers ptr1 and ptr2. Move ptr1 by N nodes. Now move ptr1 and ptr2 one node each time till ptr1 is equal to null. At this point ptr2 points to Nth node from the last.
{{{
struct node* getNthLast(struct node* node, int N){
if(node == null) return null;
struct node* ptr1,ptr2;
int i;
ptr1 = ptr2 = node;
for(i=0;i<N && ptr1 != null;i++){
ptr1 = ptr1->next;
}
if(i!=N) return null; //means LL doesn't have N nodes
if(ptr1 == null){ // case when i=N and ptr1 = null
return ptr2;
}
while(ptr1 != null){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr2;
}
}}
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.