 ### Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

XOR linked list is the memory-efficient version of the doubly linked list, in which the next pointer of every node stores the XOR of the previous and next node’s address. A XOR linked list uses only one address space per node to store the address of the previous and next node, while a doubly linked list uses two address spaces per node to store the address of the previous and next list node (prev, next).

### Problem Statement

In this problem, we are given a singly linked list and have to convert it to the XOR linked list.

### Problem Statement Understanding

In this problem, we will be discussing how we can convert a singly linked list to XOR linked list. We will be provided with a singly linked list as the input, and our task will be to somehow convert this singly linked list to a XOR linked list.  An important XOR property:

• If A XOR B = C, then A XOR C = B, as well as B XOR C = A.

### Approach

In a XOR linked list, each pointer stores the XOR of prev and next node address, so the approach is:

• First, we traverse the singly linked list and keep track of the previous node in a pointer.
• While we are traversing the list, we will change the next pointer of every node as curr.next = XOR(prev, next).

### Algorithm

1) Create three nodes:

• A current node, initially pointing to the head.
• A previous node, initially pointing to the null.
• A next node, initially pointing to the current.next.
2) Iterate while current is not null:
• Update next to current.next.
• Update current.next to XOR(prev, next).
• Update previous to current.
• Update current to next.

#### printingXOR()

• In the PrintingXOR function, we will start with a node previous, which will point to NULL, and a node current, which will point to the head.
• Now, we will print current.data.
• For the traversal, we will now need the address of the next node. We can get that by calculating address(previous node) XOR address(current.next).
• After getting the next node address, we will update our previous to current and current to the next node address.
• This process will go on till we reach the end of the list.

### Algorithm

1) Create a previous node, a current node, and a next node.
2) Make previous point to NULL and current to the head.
3) Iterate while current is not null:

• Print current.data.
• Update the previous to current and the current to the next node address.

### Code Implementation

```// Linked list node
class Node {
int data;
Node next;

Node(int item) {
data = item;
next = null;
}
}

public class PrepBytes {
static Node root;

}
System.out.println();
}

static Node XOR(Node a, Node b) {
return b;
}

// This function will convert singly linked list
Node prev = null;
Node next = current.next;

while (current != null) {

next = current.next;

current.next = XOR(prev, next);

prev = current;

current = next;
}
}

// This function will print the converted XOR linked list
Node prev = null;
Node next;

while (curr != null) {

// print current node
System.out.print(curr.data + " ");

next = XOR(prev, curr.next);
prev = curr;
curr = next;
}
System.out.println();
}

public static void main(String[] args) {

PrepBytes prep = new PrepBytes();
prep.root = new Node(53);
prep.root.next = new Node(69);
prep.root.next.next = new Node(96);
prep.root.next.next.next = new Node(27);
System.out.println("Singly Linked List Before Conversion: ");
printing(root);
convertToXOR(root);
System.out.println("After Conversion to XOR Linked List: ");
printingXOR(root);
}
}
```