Memory Efficient Doubly Linked List<\/a>.<\/p>\nHow to convert singly linked list into xor linked list <\/h2>\n
In this problem, we are given a singly linked list and have to convert it to the XOR linked list.<\/p>\n
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.<\/p>\n
Given singly linked list<\/strong><\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1657608488946-Image-01.png\")
<\/p>\n
Converted XOR linked list<\/strong><\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1657608507841-Image-02.png\")
<\/p>\n
An important XOR property:<\/strong><\/p>\n\n- If A XOR B = C<\/strong>, then A XOR C = B<\/strong>, as well as B XOR C = A<\/strong>.<\/li>\n<\/ul>\n
Approach of Convert singly linked list into xor linked list<\/h2>\n
In an XOR linked list, each pointer stores the XOR of prev and next node address, so the approach is: <\/p>\n
\n- First, we traverse the singly linked list and keep track of the previous node in a pointer. <\/li>\n
- While we are traversing the list, we will change the next pointer of every node as curr.next = XOR(prev, next)<\/strong>.<\/li>\n<\/ul>\n
Algorithm of Convert singly linked list into xor linked list<\/h2>\n\n- Create three nodes:\n
\n- A current node<\/strong>, initially pointing to the head<\/strong>.<\/li>\n
- A previous node<\/strong>, initially pointing to the null<\/strong>.<\/li>\n
- A next node<\/strong>, initially pointing to the current.next<\/strong>.<\/li>\n<\/ul>\n<\/li>\n
- Iterate while current is not null<\/strong>:\n
\n- Update next to current.next<\/strong>.<\/li>\n
- Update current.next to XOR(prev, next)<\/strong>.<\/li>\n
- Update previous to current<\/strong>.<\/li>\n
- Update current to next<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n
printingXOR()<\/strong><\/p>\n\n- In the PrintingXOR function<\/strong>, we will start with a node previous, which will point to NULL, and a node current, which will point to the head. <\/li>\n
- Now, we will print the current.data. <\/li>\n
- 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)<\/strong>. <\/li>\n
- After getting the next node address, we will update our previous to current and current to the next node address. <\/li>\n
- This process will go on till we reach the end of the list.<\/li>\n<\/ul>\n
Algorithm of Convert singly linked list into xor linked list<\/h2>\n\n- Create a previous node<\/strong>, a current node<\/strong>, and a next node<\/strong>.<\/li>\n
- Make previous point to NULL<\/strong> and current to the head<\/strong>.<\/li>\n
- \n
Iterate while current<\/strong> is not null:<\/p>\n\n- Print current.data.<\/li>\n
- Store the address of the next node as address(previous) XOR address(current.next)<\/strong>.<\/li>\n
- Update the previous to current<\/strong> and the current to the next node address<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n
Code Implementation of Convert singly linked list into xor linked list<\/h2>\n\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1657608471712-Article.jpg\")
<\/p>\n