Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on December 14, 2022 by Prepbytes

In this article, we will see another problem of linked list Convert singly linked list into xor linked list. Linked list is a linear data structures. The node in linked list consists of two parts i.e. the data and the pointer of the next node. Let’s see what exactly the XOR linked list is.

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. An 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).

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

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 an XOR linked list.

An important XOR property:

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

In an 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).

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 the 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.

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 of Convert singly linked list into xor linked list

```// 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);
}
}
```
``````Output
53 69 96 27
After Conversion to XOR Linked List:
53 69 96 27``````

Time Complexity of Convert singly linked list into xor linked list: O(n), as we are only traversing the list.

Conclusion