Pairwise swap elements of a given linked list

Pairwise swap elements of a given linked list

In this problem, we have given a linked list, and we need to pairwise swap elements of the given linked list.

Example:

                                    Input:1 ->3 ->5 ->7 ->9 ->0 ->4 ->8

                             Output:3 ->1 ->7 ->5 ->0 ->9 ->8 ->4

                             Input:2 ->6 ->5 ->1 ->9 ->0 ->3

                             Output:6 ->2 ->1 ->5 ->0 ->9 ->3

Method1:(Iterative)

In this method, we will traverse the linked list. While traversing, we will swapeach node data with its next node's data by using the iterative approach.

C Program to pairwise swap elements of the linked list by iterative method

 #include<stdio.h>
 #include<stdlib.h>
 // The structure of the node
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node * )malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start-> info = item;
 start-> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p ->next;
 }
 p-> next = t;
 p = p ->next;
 p->info = item;
 p ->next = NULL;
 }
 }
 // For swapping two elements
 void swap(int* a, int* b)
 {
 int temp;
 temp = *a;
     *a = *b;
     *b = temp;
 }
 // For the pairwise swap, the elements of the linked list
 voidpairWiseSwap(struct node* temp)
 {
 while(temp != NULL && temp ->next != NULL) {
 swap(&temp ->info, &temp ->next ->info);
 temp = temp ->next ->next;
     }
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t ->next != NULL)
                                     {
                         printf("%d  ->  ", t ->info);
                         t = t ->next;
                         }
                         printf("%d\n", t ->info);
 }
 // Driver Function
 int main()
 {
 add(1);
 add(3);
 add(5);
 add(7);
 add(9);
 add(0);
 add(4);
 add(8);
 printf("Linked List before pairwise swap:\n");
 traverse(start);
 pairWiseSwap(start);
 printf("Linked List after pairwise swap:\n");
 traverse(start);
 return 0;
 } 

Output:

Time Complexity:The time complexity of this method is O(n).         

Method2: (Recursive)

In this method, we will do recursive callsto pairwise swap elements if there are two or morenodes in the linked list.

C Program to pairwise swap elements of the linked list by a recursive method

 #include<stdio.h>
 #include<stdlib.h>
 // The structure of the node
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start = NULL;
 // For inserting the elements in the linked list
 void add(int item)
 {
 struct node * t, * p;
 t = (struct node * )malloc( sizeof( struct node ));
 if(start == NULL)
 {
 start = t;
 start ->info = item;
 start-> next = NULL;
 return;
 }
 else
 {
 struct node * p = start;
 while(p -> next != NULL)
 {
 p = p ->next;
 }
 p->next = t;
 p = p ->next;
 p->info = item;
 p ->next = NULL;
 }
 }
 // For swapping two elements
 void swap(int* a, int* b)
 {
 int temp;
 temp = *a;
     *a = *b;
     *b = temp;
 }
 // For the pairwise swap, the elements of the linked list
 voidpairWiseSwap(struct node* head)
 {
 if (head != NULL && head ->next != NULL) {
 swap(&head ->data, &head ->next ->data);
 pairWiseSwap(head ->next ->next);
     }
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
 if(t == NULL)
 {
             printf(" Linked list is empty\n");
                                     }
                                     while(t ->next != NULL)
                                     {
                         printf("%d -> ", t -> info);
                         t = t -> next;
                         }
                         printf("%d\n", t ->info);
 }
 // Driver Function
 int main()
 {
 add(1);
 add(3);
 add(5);
 add(7);
 add(9);
 add(0);
 add(4);
 add(8);
 printf("Linked List before pairwise swap:\n");
 traverse(start);
 pairWiseSwap(start);
 printf("Linked List after pairwise swap:\n");
 traverse(start);
 return 0;
 } 

Output:

Time Complexity:The time complexity of this method is O(n).