## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

METHOD 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 */

/* move the head to point to the 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 */

/* Call pairWiseSwap() for rest of the list */
}
}

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.``````

Comment hidden because of low score. Click to expand.
0

this will fail if node b appears before node a

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)

}``````

Comment hidden because of low score. Click to expand.
0

Or iteratively if you prefer

``````public static void PairSwapI(Node n)
{
while (n != null && n.next != null)
{
Node t = n.next;
Object x = n.data;
n.data = t.data;
t.data = x;
n = t.next;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

prev = 0;

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;
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.