Amazon Interview Question Software Engineer in Tests
0of 0 votesWAP to reverse pair of nodes in linked list
Swapping the nodes means swapping the links... that is what the interviewer is looking for... logic to swap the links !
... -> a.prev -> a -> b -> b.next -> ...
keep 3 pointers... a.prev , a, b
(a.prev).next = b
b.next = a
a.next=b.next
A recursive soln
Node* RecursiveReversePair(Node *head) {
Node *p = head, *q, *r;
if( !p || !(p->next)) return p;
q = p->next->next;
r = p->next;
p->next->next = p;
p->next = RecursiveReversePair(q);
return r;
}
#include<iostream>
struct node
{
struct node *next;
int value;
};
struct node *getnode()
{
return ((struct node *)malloc(sizeof(struct node *)));
}
struct node *head;
int main()
{
int n;
int val,i,flag=0,count=0;
struct node *p,*q,*r,*s,*t;
printf("Enter the number of elements in your linked list\n");
scanf("%d",&n);
printf("Enter the values in your linked list\n");
for(i=0;i<n;i++)
{
scanf("%d",&val);
if(head==NULL)
{
head=getnode();
head->value=val;
head->next=NULL;
}
else
{
p=head;
q=head;
while(p != NULL)
{
q=p;
p=p->next;
}
p=getnode();
p->value=val;
p->next=NULL;
q->next=p;
}
}
p=head;
printf("The elements in the list are \n");
//printing linked list
while(p!=NULL)
{
printf("%d \t",p->value);
p=p->next;
}
printf("\n");
p=head;
q=NULL;
r=NULL;
while(p!=NULL && p->next!=NULL)
{
q=p->next;
printf("Swapping %d and %d\n",p->value,q->value);
p->next=q->next;
q->next=p;
if(r!=NULL)
r->next=q;
if(p==head)
head=q;
r=p;
p=p->next;
}
p=head;
printf("The elements in the list are \n");
//printing linked list
while(p!=NULL)
{
printf("%d \t",p->value);
p=p->next;
}
printf("\n");
}
Can any one suggest which one is a better option in this case: adjusting the links to node or just replacing tha values of the alternate nodes.
- Rids August 06, 2011