Given a XOR linked list, the task is to pairwise swap the elements of the given XOR linked list .
Examples:
Input: 4 <-> 7 <-> 9 <-> 7
Output: 7 <-> 4 <-> 7 <-> 9
Explanation:
First pair of nodes are swapped to formed the sequence {4, 7} and second pair of nodes are swapped to form the sequence {9, 7}.Input: 1 <-> 2 <-> 3
Output: 2 <-> 1 <-> 3
Approach: The problem can be solved using the concept of Pairwise swap elements of a given linked list. The idea is to traverse the given xor-linked list and select two adjacent pair of nodes and swap them. Follow the steps below to solve the problem:
- Traverse the given xor linked-list, while current node and next node of xor linked list is not null
- In every iteration swap the data of the current node with the next node and update the pointer of the next node and the current node.
- Finally, print the xor-linked list
Below is the implementation of the above approach:
C++
#include <inttypes.h>#include <stdio.h>#include <bits/stdc++.h>using namespace std;// Structure of a node// in XOR linked liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};void pairwiseswap(struct Node**);void swap(int*, int*);// Function to find the XOR of two nodesstruct Node* XOR(struct Node* a, struct Node* b){ return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));}// Function to insert a node with// given value at given positionstruct Node* insert(struct Node** head, int value){ // If XOR linked list is empty if (*head == NULL) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Stores data value in // the node node->data = value; // Stores XOR of previous // and next pointer node->nxp = XOR(NULL, NULL); // Update pointer of head node *head = node; } // If the XOR linked list // is not empty else { // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Update curr node address curr->nxp = XOR(node, XOR(NULL, curr->nxp)); // Update new node address node->nxp = XOR(NULL, curr); // Update head *head = node; // Update data value of // current node node->data = value; } return *head;}// Function to pairwise swap the nodes// of the XOR-linked listvoid pairwiseswap(struct Node** head){ // Stores pointer of current node struct Node* curr = (*head); // Stores pointer of previous node struct Node* prev = NULL; // Stores pointer of next node struct Node* next = NULL; // Traverse the XOR-linked list while (curr != NULL && curr->nxp != XOR(prev, NULL)) { next = XOR(prev, curr->nxp); prev = curr; curr = next; // Swap the elements swap(&prev->data, &curr->data); // Update next next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; }}// Function to swap two numbersvoid swap(int* a, int* b){ int temp; temp = *a; *a = *b; *b = temp;}// Function to print elements of// the XOR Linked Listvoid printList(struct Node** head){ // Stores XOR pointer // in current node struct Node* curr = *head; // Stores XOR pointer of // in previous Node struct Node* prev = NULL; // Stores XOR pointer of // in next node struct Node* next; // Traverse XOR linked list while (curr != NULL) { // Print current node cout<< curr->data<< " "; // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; }}// Driver Codeint main(){ /* Create following XOR Linked List head -->7 –> 6 –>8 –> 11 –> 3 –> 1 –> 2 –> 0*/ struct Node* head = NULL; insert(&head, 0); insert(&head, 2); insert(&head, 1); insert(&head, 3); insert(&head, 11); insert(&head, 8); insert(&head, 6); insert(&head, 7); // Swap the elements pairwise pairwiseswap(&head); // Print the new list printList(&head); return (0);}// This code is contributed by lokeshpotta20. |
C
// C++ program to implement// the above approach#include <inttypes.h>#include <stdio.h>#include <stdlib.h>// Structure of a node// in XOR linked liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};void pairwiseswap(struct Node**);void swap(int*, int*);// Function to find the XOR of two nodesstruct Node* XOR(struct Node* a, struct Node* b){ return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));}// Function to insert a node with// given value at given positionstruct Node* insert(struct Node** head, int value){ // If XOR linked list is empty if (*head == NULL) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Stores data value in // the node node->data = value; // Stores XOR of previous // and next pointer node->nxp = XOR(NULL, NULL); // Update pointer of head node *head = node; } // If the XOR linked list // is not empty else { // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Update curr node address curr->nxp = XOR(node, XOR(NULL, curr->nxp)); // Update new node address node->nxp = XOR(NULL, curr); // Update head *head = node; // Update data value of // current node node->data = value; } return *head;}// Function to pairwise swap the nodes// of the XOR-linked listvoid pairwiseswap(struct Node** head){ // Stores pointer of current node struct Node* curr = (*head); // Stores pointer of previous node struct Node* prev = NULL; // Stores pointer of next node struct Node* next = NULL; // Traverse the XOR-linked list while (curr != NULL && curr->nxp != XOR(prev, NULL)) { next = XOR(prev, curr->nxp); prev = curr; curr = next; // Swap the elements swap(&prev->data, &curr->data); // Update next next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; }}// Function to swap two numbersvoid swap(int* a, int* b){ int temp; temp = *a; *a = *b; *b = temp;}// Function to print elements of// the XOR Linked Listvoid printList(struct Node** head){ // Stores XOR pointer // in current node struct Node* curr = *head; // Stores XOR pointer of // in previous Node struct Node* prev = NULL; // Stores XOR pointer of // in next node struct Node* next; // Traverse XOR linked list while (curr != NULL) { // Print current node printf("%d ", curr->data); // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; }}// Driver Codeint main(){ /* Create following XOR Linked List head -->7 –> 6 –>8 –> 11 –> 3 –> 1 –> 2 –> 0*/ struct Node* head = NULL; insert(&head, 0); insert(&head, 2); insert(&head, 1); insert(&head, 3); insert(&head, 11); insert(&head, 8); insert(&head, 6); insert(&head, 7); // Swap the elements pairwise pairwiseswap(&head); // Print the new list printList(&head); return (0);} |
Output:
6 7 11 8 1 3 0 2
Time Complexity: O(N)
Auxiliary Space: O(1), as it does not allocate any additional memory. The insert function is also O(1) as it only performs a constant amount of operations to add a new node to the list.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
