Given a singly linked list, write a function to swap elements pairwise.
Input: 1->2->3->4->5->6->NULL Output: 2->1->4->3->6->5->NULL Input: 1->2->3->4->5->NULL Output: 2->1->4->3->5->NULL Input: 1->NULL Output: 1->NULL
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 then the function should change it to.
METHOD (Iterative):
Start from the head node and traverse the list. While traversing swap data of each node with its next node’s data.
Below is the implementation of the above approach:
C++
// C++ program to pairwise swap elements // in a given linked list #include <bits/stdc++.h> using namespace std; // A linked list node class Node { public: int data; Node* next; }; /* Function to pairwise swap elements of a linked list */void pairWiseSwap(Node* head) { 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; } } /* Function to add a node at the beginning of Linked List */void push(Node** head_ref, int new_data) { // Allocate node Node* new_node = new 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(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } // Driver Code int main() { 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); cout << "Linked list " << "before calling pairWiseSwap()"; printList(start); pairWiseSwap(start); cout << "Linked list " << "after calling pairWiseSwap()"; printList(start); return 0; } // This code is contributed by rathbhupendra |
Output:
Linked list before calling pairWiseSwap() 1 2 3 4 5 Linked list after calling pairWiseSwap() 2 1 4 3 5
Time complexity: O(n)
Auxiliary Space: O(1)
Please refer complete article on Pairwise swap elements of a given linked list for more details!
