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