Tuesday, May 14, 2013

Reverse adjacent nodes in a linked list

Reverse the adjacent nodes in a linked list If the nodes of a linked list are as follows 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 then after reverse they should be 2 -> 1 -> 4 -> 3 Here the number of entries are odd hence the last link is not reversed. If number of nodes are even then last node should also be reversed.

node * swapAdjacent(node * head){
node *a,*b,*c,*d;
a = head;
if(a == null)
return a;
b = a->next;
if(b == null)
return a;
c = b->next;
if(c == null){
b->next = a;
a->next = c;
return b;
}
d = c->next;

//now all a,b,c are non null. size of list is >=3
node * newHead = b;
while(b!= null){
b->next = a;
if(d != null)
a->next = d;
else
a->next = c;
a = c;
b = d;
c = (b!=null)?b->next : null;
d = (c!=null)?c->next : null;
}
return newHead;
}

No comments: