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.