XOR Linked List β Pairwise swap elements of a given linked list
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:
#include <inttypes.h>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
// in XOR linked list
struct 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 nodes
struct 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 position
struct 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 list
void 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 numbers
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Function to print elements of
// the XOR Linked List
void 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 Code
int 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++ program to implement
// the above approach
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
// Structure of a node
// in XOR linked list
struct 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 nodes
struct 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 position
struct 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 list
void 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 numbers
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Function to print elements of
// the XOR Linked List
void 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 Code
int 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);
}
// Java program for the above approach
import java.util.*;
// Structure of a node in XOR linked list
class Node {
// Stores data value of a node
int data;
// Stores XOR of previous pointer and next pointer
Node nxp;
// Constructor to initialize node
Node(int data)
{
this.data = data;
this.nxp = null;
}
}
class XorLinkedList {
Node head; // head of list
// Function to insert a node with given value at given
// position
void insert(int value)
{
// Initialize a new Node
Node node = new Node(value);
// Stores XOR of previous and next pointer
node.nxp = head;
// Update pointer of head node
head = node;
}
// Function to pairwise swap the nodes of the XOR-linked
// list
void pairwiseswap()
{
// If head is null
if (head == null || head.nxp == null)
return;
// Stores pointer of current node
Node curr = head;
// Update head
head = head.nxp;
// Stores pointer of previous node
Node prev = null;
// Stores pointer of next node
Node next = null;
// Stores prev node of prev pair
Node pPrev = null;
// Traverse the XOR-linked list
while (curr != null) {
// Update next
next = curr.nxp;
// Update prev
prev = curr;
// Update curr
curr = next;
// Swap the elements
prev.nxp = next.nxp;
curr.nxp = prev;
if (pPrev != null)
pPrev.nxp = curr;
// Update next
next = prev.nxp;
// Update pPrev
pPrev = prev;
// Update curr
curr = next;
}
}
// Function to print elements of the XOR Linked List
void printList()
{
// Stores XOR pointer in current node
Node curr = this.head;
// Traverse XOR linked list
while (curr != null) {
// Print current node
System.out.print(curr.data + " ");
// Update curr
curr = curr.nxp;
}
}
}
// Main method
public class GFG {
public static void main(String[] args)
{
// Stores number of nodes
int N = 8;
// Given XOR Linked List
XorLinkedList xll = new XorLinkedList();
xll.insert(0);
xll.insert(2);
xll.insert(1);
xll.insert(3);
xll.insert(11);
xll.insert(8);
xll.insert(6);
xll.insert(7);
// Swap the elements pairwise
xll.pairwiseswap();
// Print the new list
xll.printList();
}
}
// This code is contributed by Susobhan Akhuli
class Node {
constructor(data) {
this.data = data;
this.nxp = null; // Stores XOR of previous pointer and next pointer
}
}
class XorLinkedList {
constructor() {
this.head = null; // head of list
}
// Function to insert a node with given value at the beginning
insert(value) {
// Initialize a new Node
const node = new Node(value);
// Stores XOR of previous and next pointer
node.nxp = this.head;
// Update pointer of head node
this.head = node;
}
// Function to pairwise swap the nodes of the XOR-linked list
pairwiseswap() {
// If head is null or only one node present
if (!this.head || !this.head.nxp) {
return;
}
// Stores pointer of current node
let curr = this.head;
// Update head
this.head = this.head.nxp;
// Stores pointer of previous node
let prev = null;
// Stores pointer of next node
let next = null;
// Stores prev node of prev pair
let pPrev = null;
// Traverse the XOR-linked list
while (curr) {
// Update next
next = curr.nxp;
// Update prev
prev = curr;
// Update curr
curr = next;
// Swap the elements
prev.nxp = next.nxp;
curr.nxp = prev;
if (pPrev) {
pPrev.nxp = curr;
}
// Update next
next = prev.nxp;
// Update pPrev
pPrev = prev;
// Update curr
curr = next;
}
}
// Function to print elements of the XOR Linked List
printList() {
// Stores XOR pointer in current node
let curr = this.head;
// Traverse XOR linked list
while (curr) {
// Print current node
console.log(curr.data);
// Update curr
curr = curr.nxp;
}
}
}
// Main method
function main() {
// Given XOR Linked List
const xll = new XorLinkedList();
xll.insert(0);
xll.insert(2);
xll.insert(1);
xll.insert(3);
xll.insert(11);
xll.insert(8);
xll.insert(6);
xll.insert(7);
// Swap the elements pairwise
xll.pairwiseswap();
// Print the new list
xll.printList();
}
// Calling the main method
main();
# Python program for the above approach
class Node:
def __init__(self, data):
self.data = data
self.nxp = None # Stores XOR of previous pointer and next pointer
class XorLinkedList:
def __init__(self):
self.head = None # head of list
# Function to insert a node with given value at given position
def insert(self, value):
# Initialize a new Node
node = Node(value)
# Stores XOR of previous and next pointer
node.nxp = self.head
# Update pointer of head node
self.head = node
# Function to pairwise swap the nodes of the XOR-linked list
def pairwiseswap(self):
# If head is null or head's next pointer is null, return
if self.head is None or self.head.nxp is None:
return
# Stores pointer of current node
curr = self.head
# Update head
self.head = self.head.nxp
# Stores pointer of previous node
prev = None
# Stores pointer of next node
next = None
# Stores prev node of prev pair
pPrev = None
# Traverse the XOR-linked list
while curr is not None:
# Update next
next = curr.nxp
# Update prev
prev = curr
# Update curr
curr = next
# Swap the elements
prev.nxp = next.nxp
curr.nxp = prev
if pPrev is not None:
pPrev.nxp = curr
# Update next
next = prev.nxp
# Update pPrev
pPrev = prev
# Update curr
curr = next
# Function to print elements of the XOR Linked List
def printList(self):
# Stores XOR pointer in current node
curr = self.head
# Traverse XOR linked list
while curr is not None:
# Print current node
print(curr.data, end=" ")
# Update curr
curr = curr.nxp
# Main method
if __name__ == "__main__":
# Stores number of nodes
N = 8
# Given XOR Linked List
xll = XorLinkedList()
xll.insert(0)
xll.insert(2)
xll.insert(1)
xll.insert(3)
xll.insert(11)
xll.insert(8)
xll.insert(6)
xll.insert(7)
# Swap the elements pairwise
xll.pairwiseswap()
# Print the new list
xll.printList()
# This code is contributed by Susobhan Akhuli
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.