Saturday, March 1, 2014

Pairwise swap elements of a given linked list by changing links


// Head of linkedlist has to change for pairwise swap and returns head of linkedlist.

Method #1.

static listNode pairwiseSwap(listNode head)
{
if(head == null || head.next == null) return head;
listNode curr, tmp, oldhead;
// Initial swap of two nodes
oldhead = head;

tmp = head.next;
head = tmp;
//head = head.next;
oldhead.next = oldhead.next.next;
tmp.next = oldhead;


for(curr = oldhead.next; curr != null && curr.next != null; curr = curr.next)
{
tmp = curr.next;
curr.next = curr.next.next;
tmp.next = curr;
oldhead.next = tmp;
oldhead = curr;
}
return head;
}


Method #2.

static listNode swapPairWise(listNode head){
if(head == null || head.next == null) return head;

listNode curr = head;

if(head.next.next == null)
{

head = curr.next;
head.next = curr;
curr.next = null;
}else{

listNode next = curr.next.next;
head = curr.next;
head.next = curr;
listNode tail = head.next;
tail.next = null;

while(next != null && next.next != null)
{
curr = next;
next = next.next.next;
curr.next.next = curr;
tail.next = curr.next;
tail = curr;
tail.next = null;
}
if(next != null && next.next == null)
tail.next = next;
}


return head;
}

Method #3.

static listNode swapRecursive(listNode head){
if(head == null || head.next == null) return head;

listNode next= head.next.next, newhead = head.next;
head.next.next = head;
head.next = swapPairWise(next);

return newhead;
}

References:
http://www.geeksforgeeks.org/pairwise-swap-elements-of-a-given-linked-list-by-changing-links/

No comments:

Post a Comment