## Interview Question

**Country:**United States

```
node *swap(node *pt,node *a,node *b)
{
node *root=pt;
node *x_l,*x_r;
node *y_l,*y_r;
node *prev=NULL;
while(pt!=b)
{
if(pt==a)
{
x_l=prev;
x_r=pt->next;
}
prev=pt;
pt=pt->next;
}
y_l=prev;
y_r=pt->next;
x_l->next=b;
b->next=x_r;
y_l->next=a;
a->next=y_r;
return root;
};
head is passed in first argument.
```

```
void swap_pairs(Node* list) {
if (!list) return;
Node* before = NULL;
Node* first = list;
Node* second = list->next;
Node* after = second ? second->next : NULL;
while (first && second) {
if (before) before->next = second;
second->next = first;
first->next = after;
first = after;
second = first ? first->next : NULL;
after = second ? second->next : NULL;
}
}
```

```
void PairSwap(node x)
{
if(x== null || x.next == null)
return;
node t = x.next;
object d = x.data;
x.data = t.data;
t.data = d;
PairSwap(t.next)
}
```

Solution with O(n) complexity

swap_ptr(list *p1, list *p2)

{

temp = p2->next;

p2->next = p1;

p1->next = temp

}

void swap_list_pair(list * head)

{

if (head == 0 && head->next == 0)

return head;

prev = 0;

node = head;

head = head->next; // new head

while (node && node->next)

{

first = node;

second = node->next;

node = node->next->next;

swap_ptr(first,second);

// after this first node became second and second became first

if(prev)

prev->next = second;

prev = first;

}

return head;

}

Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.

- ansariinjnu October 03, 2012METHOD 1 (Iterative)

Start from the head node and traverse the list. While traversing swap data of each node with its next node’s data.

/* Program to pairwise swap elements in a given linked list */

#include<stdio.h>

#include<stdlib.h>

/* A linked list node */

struct node

{

int data;

struct node *next;

};

/*Function to swap two integers at addresses a and b */

void swap(int *a, int *b);

/* Function to pairwise swap elements of a linked list */

void pairWiseSwap(struct node *head)

{

struct node *temp = head;

/* Traverse further only if there are at-least two nodes left */

while(temp != NULL && temp->next != NULL)

{

/* Swap data of node with its next node's data */

swap(&temp->data, &temp->next->data);

/* Move temp by 2 for the next pair */

temp = temp->next->next;

}

}

/* UTILITY FUNCTIONS */

/* Function to swap two integers */

void swap(int *a, int *b)

{

int temp;

temp = *a;

*a = *b;

*b = temp;

}

/* Function to add a node at the begining of Linked List */

void push(struct node** head_ref, int new_data)

{

/* allocate node */

struct node* new_node =

(struct node*) malloc(sizeof(struct node));

/* put in the data */

new_node->data = new_data;

/* link the old list off the new node */

new_node->next = (*head_ref);

/* move the head to point to the new node */

(*head_ref) = new_node;

}

/* Function to print nodes in a given linked list */

void printList(struct node *node)

{

while(node != NULL)

{

printf("%d ", node->data);

node = node->next;

}

}

/* Druver program to test above function */

int main()

{

struct node *start = NULL;

/* The constructed linked list is:

1->2->3->4->5 */

push(&start, 5);

push(&start, 4);

push(&start, 3);

push(&start, 2);

push(&start, 1);

printf("\n Linked list before calling pairWiseSwap() ");

printList(start);

pairWiseSwap(start);

printf("\n Linked list after calling pairWiseSwap() ");

printList(start);

getchar();

return 0;

}

Time complexity: O(n)

METHOD 2 (Recursive)

If there are 2 or more than 2 nodes in Linked List then swap the first two nodes and recursively call for rest of the list.

/* 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);

}

}

Time complexity: O(n)

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.