Convert Singly Linked List to XOR Linked List
Last Updated :
15 Sep, 2022
Prerequisite:
An XOR linked list is a memory efficient doubly linked list in which the next pointer of every node stores the XOR of previous and next node’s address.
Given a singly linked list, the task is to convert the given singly list to a XOR linked list.
Approach: Since in XOR linked list each next pointer stores the XOR of prev and next nodes’s address. So the idea is to traverse the given singly linked list and keep track of the previous node in a pointer say prev.
Now, while traversing the list, change the next pointer of every node as:
current -> next = XOR(prev, current->next)
Printing the XOR linked list:
While printing XOR linked list we have to find the exact address of the next node every time. As we have seen above that the next pointer of every node stores the XOR value of prev and next node’s address. Therefore, the next node’s address can be obtained by finding XOR of prev and next pointer of current node in the XOR linked list.
So, to print the XOR linked list, traverse it by maintaining a prev pointer which stores the address of the previous node and to find the next node, calculate XOR of prev with next of current node.
Below is the implementation of the above approach:
CPP
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
void print(Node* head)
{
while (head) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
Node* XOR(Node* a, Node* b)
{
return (Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}
void convert(Node* head)
{
Node* curr = head;
Node* prev = NULL;
Node* next = curr->next;
while (curr) {
next = curr->next;
curr->next = XOR(prev, next);
prev = curr;
curr = next;
}
}
void printXOR(Node* head)
{
Node* curr = head;
Node* prev = NULL;
while (curr) {
cout << curr->data << " ";
Node* temp = curr;
curr = XOR(prev, curr->next);
prev = temp;
}
cout << endl;
}
int main()
{
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
cout << "Before Conversion : " << endl;
print(head);
convert(head);
cout << "After Conversion : " << endl;
printXOR(head);
return 0;
}
|
Java
import java.io.*;
class Node
{
int data;
Node next;
Node(int item)
{
data = item;
next = null;
}
}
class GFG
{
public static Node root;
static void print(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
static Node XOR(Node a, Node b)
{
return b;
}
static void convert(Node head)
{
Node curr = head;
Node prev = null;
Node next = curr.next;
while(curr != null)
{
next = curr.next;
curr.next = XOR(prev, next);
prev = curr;
curr = next;
}
}
static void printXOR(Node head)
{
Node curr = head;
Node prev = null;
while(curr != null)
{
System.out.print(curr.data + " ");
Node temp = curr;
curr = XOR(prev, curr.next);
prev = temp;
}
System.out.println();
}
public static void main (String[] args)
{
GFG tree = new GFG();
tree.root = new Node(1);
tree.root.next = new Node(2);
tree.root.next.next = new Node(3);
tree.root.next.next.next = new Node(4);
System.out.println("Before Conversion : ");
print(root);
convert(root);
System.out.println("After Conversion : ");
printXOR(root);
}
}
|
Python3
class Node:
def __init__(self,d):
self.data = d
self.next = None
def printt(head):
while (head):
print(head.data, end=" ")
head = head.next
print()
def XOR(a, b):
return b
def convert(head):
curr = head
prev = None
next = curr.next
while (curr):
next = curr.next
curr.next = XOR(prev, next)
prev = curr
curr = next
def printXOR(head):
curr = head
prev = None
while (curr):
print(curr.data, end=" ")
temp = curr
curr = XOR(prev, curr.next)
prev = temp
print()
if __name__ == '__main__':
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
print("Before Conversion : ")
printt(head)
convert(head)
print("After Conversion : ")
printXOR(head)
|
C#
using System;
class Node
{
public int data;
public Node next;
public Node(int item)
{
data = item;
next = null;
}
}
public class GFG
{
static Node root;
static void print(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine();
}
static Node XOR(Node a, Node b)
{
return b;
}
static void convert(Node head)
{
Node curr = head;
Node prev = null;
Node next = curr.next;
while(curr != null)
{
next = curr.next;
curr.next = XOR(prev, next);
prev = curr;
curr = next;
}
}
static void printXOR(Node head)
{
Node curr = head;
Node prev = null;
while(curr != null)
{
Console.Write(curr.data + " ");
Node temp = curr;
curr = XOR(prev, curr.next);
prev = temp;
}
Console.WriteLine();
}
static public void Main ()
{
GFG.root = new Node(1);
GFG.root.next = new Node(2);
GFG.root.next.next = new Node(3);
GFG.root.next.next.next = new Node(4);
Console.WriteLine("Before Conversion : ");
print(root);
convert(root);
Console.WriteLine("After Conversion : ");
printXOR(root);
}
}
|
Javascript
<script>
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var root;
function print( head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
document.write("<br/>");
}
function XOR( a, b) {
return b;
}
function convert( head) {
var curr = head;
var prev = null;
var next = curr.next;
while (curr != null) {
next = curr.next;
curr.next = XOR(prev, next);
prev = curr;
curr = next;
}
}
function printXOR( head) {
var curr = head;
var prev = null;
while (curr != null) {
document.write(curr.data + " ");
var temp = curr;
curr = XOR(prev, curr.next);
prev = temp;
}
document.write();
}
root = new Node(1);
root.next = new Node(2);
root.next.next = new Node(3);
root.next.next.next = new Node(4);
document.write("Before Conversion : <br/>");
print(root);
convert(root);
document.write("After Conversion : <br/>");
printXOR(root);
</script>
|
Output
Before Conversion :
1 2 3 4
After Conversion :
1 2 3 4
Complexity Analysis:
- Time complexity: O(N) where N is no of nodes in given linked list
- Auxiliary Space: O(1)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...