CareerCup

public static Node PairWiseSwap(Node root) {

        if (root == null || root.next == null) 
        {
             return root;
        }
        Node a = root;
        Node b = root.next; 
     
        root = b;    // after swap b will be the head of the list
    
        do  {
                a.next = b.next;
                b.next = a;
                b.prev = a.prev;
                a.prev = b;
             
                //   Example in list a,b,c,d    after swapping nodes 'a' & 'b' pointers , 'c.prev' should be made point to 'a' now .. The list will be b,a,c,d  now . After swapping 'c' & 'd' , a.next should be set to d . Now the list is b,a,d,c

                if (a.next != null) 
                {
                    a.next.prev = a;
                }


                if(b.prev != null)
                {
                    b.prev.next = b;
                }
                a = a.next;
                b = (a != null)? a.next : null; 

        } while ( a != null && b != null)	
        return root;	
}

Check this out:

void PairWiseSwap(Node** mainlist)
{
	if (mainlist && *mainlist)
	{
		Node* list = *mainlist;
		Node* temp = list->next;
		if (temp)
		{
			*mainlist = temp;
			while(temp)
			{
				list->next = temp->next;
				temp->next = list;
				temp->prev = list->prev;
				list->prev = temp;
				if (temp->prev)
					temp->prev->next = temp;
				if (list ->next)
					list ->next->prev = list ;
				list = temp->next;
				if (list)
					temp = list->next;
				else
					temp = 0;
			}
		}
	}
}

I am assuming your question is

x<->z<->a<->b should be changed to

z<->x<->b<->a

not using pointer voodoo, cant we just swap the element values ?

answer suggestion:

public Node SwapPairWise(Node list)
{
Node nextList=null,prev=null,next=null,cur=null;
if(list!=null)
{
cur=list;
}
else
{
return null;
}
list=cur.Next;
while(cur!=null)
{
nextList=cur.Next.Next;
prev=cur.Prev;
next=cur.Next;
next.Next=cur;
cur.Prev=next;
cur.Next=nextList;
if(nextList!=null)
{
nextList.prev=cur;
}
next.Prev=prev;
if(prev!=null)
{
prev.Next=next;
}
cur=nextList;
}

return list


}

This is a modified version of reversing a doubly linked list. At the end we traverse back to the beginning to update the head node.

public void swapPairsInList(Node head) {
        if (head == null || head.next == null) {
            return; // 0 or 1 node
        }

        Node p;
        Node q;
        Node r = head;

        while (r != null && r.next != null) {

            p = r;
            q = r.next;
            r = q.next;

            q.prev = p.prev;
            if (p.prev != null) {
                p.prev.next = q;
            }

            p.prev = q;
            p.next = q.next;
            if (q.next != null) {
                q.next.prev = p;
            }

            q.next = p;

        }
        
        while(p.prev != null) {
            p = p.prev;
        }
        
        this.head = p;
    }

HERE,

A<=>B<=>C

then for iteration 1 A is startp and B is endp;
     for iteration 2 C is startp and endp is null. Hence, break;
At the end, end is travesed till right head position.


void SwapPairElements()
{
if(head == 0)
	return;
else
{
	Node *startp = head;
	Node *endp   = null;
	
	while(startp)
	{
		endp = startp->next;
		if(endp)
		{
			startp->next = endp->next;
			endp->next = startp;
			endp->prev = startp->prev;
			startp->prev = endp;
			if(startp->next)
				startp->next->prev = startp;
			if(endp->prev)
				endp->prev->next = endp;
			
			startp = startp->next;
		}
		else {
			endp = startp;
			break;
		}	   
	}	
}

while(endp->prev != null)
	endp= endp>prev;

head = endp;
}

node* swap_alt_nodes(node *head)
{
node *temp1, *temp2;
int flag = 1;

temp1 = head;

while(temp1->next)
{
temp2 = temp1->next;
temp3 = temp2->next;

Swap(&temp1,&temp2);
if(flag)
{
head = temp2;
flag = 0;
}

temp1 = temp3;
}
return head;
}

node* swapPair(struct node *head)
{
if(!head || !(head->next))
return head;

struct node* curr=head;
struct node* succ=curr->next->next;

curr->next->next=curr;
curr->prev=curr->next;
curr->next=swapPair(succ);
curr->prev->prev=NULL;
if(curr->next)
curr->next->prev=curr;

return (curr->prev);

}

I generalized the solution to swap every 'k' elements:

public static Node swapKElements(Node head, int k) {

		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return head;
		}

		Node current = head;
		Node next = head.next;
		current.next = null;
		current.prev = null;
		int i = 0;
		while (next != null && i < k - 1) {
			Node temp = next.next;
			next.next = current;
			next.prev = current.prev;
			current.prev = next;
			current = next;
			next = temp;
			i++;
		}
		if (next != null) {
			head.next = swapKElements(next, k);
			if (head.next != null) {
				head.next.prev = head;
			}
		}

		return current;
	}