CareerCup

divide linklist into two parts:

a->c->e->g...
and
b->d->f->h....

now change the order subLinkList

secondListNode->firstListNode

b->a->d->c->f->e->....

/* Recursive function to pairwise swap elements of a linked list */
void pairWiseSwap(struct node *head)
{
/* There must be at-least two nodes in the list */
if(head != NULL && head->next != NULL)
{
/* Swap the node's data with data of next node */
swap(&head->data, &head->next->data);

/* Call pairWiseSwap() for rest of the list */
pairWiseSwap(head->next->next);
}
}

In C

void swap_every_two(node **head) {
  node *current = *head;
  node *next = NULL;
  node *prev = NULL;
  if (head == NULL)
    return;
  if (*head == NULL) /* no elements */
    return;
  if ((*head)->next == NULL) /* only one element */
    return;
  *head = current->next; /* update the head pointer */
  next = current->next;
  current->next = next->next;
  next->next = current;
  prev = current;
  current = current->next;
  while (current != NULL && current->next != NULL) {
    next = current->next;
    current->next = next->next;
    next->next = current;
    prev->next = next;
    prev = current;
    current = current->next;
  }
}

@pkt
how u divide the list.. using 2 pointers ? still it'll be O(n)

Guys i feel we shud ask the interviewer whether we need to swap on data of nodes in pair or the entire node itself.

Node<V> pairReverse(Node<V> head)
	{
		if(head!=null)
		{
			Node<V> prev, cur,bk=null;
			prev = head;
			cur = head.next;
			head = cur;
			do
			{
				if(bk!=null)
					bk.next = cur;
				prev.next = cur.next;
				cur.next = prev;
				bk=prev;
				prev = prev.next;
				if(prev!=null)
					cur=prev.next;
				
			}while(prev!=null);
		}
		return head;
	}

string reverse(string rev){
      for(int i = 0; i < rev.length()/2 i++){
         char temp = rev[length - i];
         rev[length - i] = rev[i];
         rev[i] = temp;
      }

   }

#include<iostream>
#include<conio.h>
using namespace std;

struct node
{
       int data;
       node *next;
};

node *list;

void insert()
{
     int num;
     node *tmp;
     node *a;
     cout<<"enter data : ";
     cin>>num;
     if(list == NULL)
     {
             list = (struct node *)malloc(sizeof(struct node));
             list->data = num;
             list->next = NULL;
     }
     else
     {
             tmp = list;
             while(tmp->next != NULL)
             tmp = tmp->next;
             a = (struct node *)malloc(sizeof(struct node));
             a->data = num;
             tmp->next = a;
             a->next = NULL;
     }
}

void display()
{
     node *tmp = list;
     while(tmp != NULL)
     {
               cout<<tmp->data<<" -> ";
               tmp = tmp->next;
     }
     cout<<"null\n";
}

void pairSwap()
{
     node *tmp = list;
     while(tmp != NULL && tmp->next != NULL)
     {
                     int a = tmp->next->data;
                     tmp->next->data = tmp->data;
                     tmp->data = a;
                     tmp = tmp->next->next;
     }
}

int main()
{
    int ch;
    do{
    cout<<"**************************  MENU  **************************\n\n";
    cout<<"\t\t1.  Wana add more data to the list \n";
    cout<<"\t\t2.  Wana display \n";
    cout<<"\t\t3.  Swap pairs in list \n";
    cout<<"\t\t4.  Empty the list \n";
    cout<<"\t\t5.  Exit \n\n";
    cin>>ch;
    switch(ch)
    {
              case 1: insert();break;
              case 2: display();getch();break;
              case 3: pairSwap();break;
              case 4: list = NULL;break;
              case 5: exit(1);
              default: cout<<"Wrong choice... Try again \n\n";
    }
    system("cls");
    }while(1);
    system("pause");
    return 0;
}

Full code written. Please comment if you don't understand or its taking too much time
to execute or its not what was asked for.

Thanks in advance...

Simple recursive solution
{{public Node swap (Node root)
{
if (root==null) return null;
if (root.next==null) return root;
Node first, second;
first = root;
second = root.next;
first.next= swap(second.next);
second.next=first;
return second;
}}}

ignore extra braces at start and end

<pre lang="" line="1" title="CodeMonkey33975" class="run-this"> public void reversePair(){
LinkedListNode previous=head.link; // First Element
LinkedListNode current=head.link.link; // Second Element
LinkedListNode tmp=null;
LinkedListNode tmp2=null;
head.link=current;
while(previous.link!=null && current.link!=null){
tmp=current.link;
tmp2=previous;

previous.link=current.link.link;
current.link=previous;

previous=tmp;
current=tmp.link;

}
if(previous.link!=null){
previous.link=current.link;
current.link=previous;
}
else{
tmp2.link=previous;
}
}
</pre><pre title="CodeMonkey33975" input="yes">
</pre>

// 1-2-3-4-5-6-7
// 2-1-4-3-6-5-7
ListNode* PairReversal(ListNode* root)
{
ListNode* nodeToReturn = root->mNext;
while (root != NULL && root->mNext != NULL) {
ListNode* nextNode = root->mNext;
ListNode* nextNext = nextNode->mNext;
nextNode->mNext = root;
if (nextNext->mNext != NULL) {
root->mNext = nextNext->mNext;
}
else {
root->mNext = nextNext;
}
root = nextNext;
}

return nodeToReturn;
}

// 1-2-3-4-5-6-7
// 2-1-4-3-6-5-7
ListNode* PairReversal(ListNode* root)
{
	ListNode* nodeToReturn = root->mNext;
	while (root != NULL && root->mNext != NULL) {
		ListNode* nextNode = root->mNext;
		ListNode* nextNext = nextNode->mNext;
		nextNode->mNext = root;
		if (nextNext->mNext != NULL) {
			root->mNext = nextNext->mNext;
		}
		else {
			root->mNext = nextNext;
		}
		root = nextNext;
	}

	return nodeToReturn;
}

ListNode reversePair(ListNode head) {
    ListNode newHead = head;
    ListNode w = null;
    ListNode p = head;
    ListNode q = null;
    if (p != null && p.next != null) {
      q = p.next;
      newHead = q;
    }
    while (p != null && q != null) {
      ListNode tmp = q.next;
      q.next = p;
      p.next = tmp;
      if (w != null)
        w.next = q;
      w = p;
      p = p.next;
      if (p != null)
        q = p.next;
    }
    return newHead;
  }