Given an XOR linked list, the task is to find the middle node of the given XOR linked list.
Examples:
Input: 4 –> 7 –> 5
Output: 7
Explanation:
The middle node of the given XOR list is 7.Input: 4 –> 7 –> 5 –> 1
Output: 7 5
Explanation:
The two middle nodes of the XOR linked list with even number of nodes are 7 and 5.
Approach: Follow the steps below to solve the problem:
- Traverse to (Length / 2)th node of the Linked List.
- If the number of nodes is found to be odd, then print (Length + 1) / 2 th node as the only middle node.
- If the number of nodes is found to be even, then print both Length / 2 th node and (Length / 2) + 1 th node as the middle nodes.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>#include <inttypes.h>using namespace std;// Structure of a node// in XOR linked liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};// Function to find the XOR of two nodesstruct 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 positionstruct Node* insert(struct Node** head, int value){ // If XOR linked list is empty if (*head == NULL) { // Initialize a new Node struct Node* node = new 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 = new 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 print the middle nodeint printMiddle(struct Node** head, int len){ int count = 0; // 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; int middle = (int)len / 2; // Traverse XOR linked list while (count != middle) { // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; count++; } // If the length of the // linked list is odd if (len & 1) { cout << curr->data << " "; } // If the length of the // linked list is even else { cout << prev->data << " " << curr->data << " "; }}// Driver Codeint main(){ /* Create following XOR Linked List head --> 4 –> 7 –> 5 */ struct Node* head = NULL; insert(&head, 4); insert(&head, 7); insert(&head, 5); printMiddle(&head, 3); return (0);} |
C
// C program to implement// the above approach#include <inttypes.h>#include <stdio.h>#include <stdlib.h>// Structure of a node// in XOR linked liststruct Node { // Stores data value // of a node int data; // Stores XOR of previous // pointer and next pointer struct Node* nxp;};// Function to find the XOR of two nodesstruct 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 positionstruct 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 print the middle nodeint printMiddle(struct Node** head, int len){ int count = 0; // 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; int middle = (int)len / 2; // Traverse XOR linked list while (count != middle) { // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; count++; } // If the length of the // linked list is odd if (len & 1) { printf("%d", curr->data); } // If the length of the // linked list is even else { printf("%d %d", prev->data, curr->data); }}// Driver Codeint main(){ /* Create following XOR Linked List head --> 4 –> 7 –> 5 */ struct Node* head = NULL; insert(&head, 4); insert(&head, 7); insert(&head, 5); printMiddle(&head, 3); return (0);} |
Python3
# C program to implement# the above approachimport ctypes# Structure of a node in XOR linked listclass Node: def __init__(self, value): self.value = value self.npx = 0# create linked list classclass XorLinkedList: # constructor def __init__(self): self.head = None self.tail = None self.__nodes = [] # Function to insert a node with given value at given position def insert(self, value): # Initialize a new Node node = Node(value) # Check If XOR linked list is empty if self.head is None: # Update pointer of head node self.head = node # Update pointer of tail node self.tail = node else: # Update curr node address self.head.npx = id(node) ^ self.head.npx # Update new node address node.npx = id(self.head) # Update head self.head = node # push node self.__nodes.append(node) # method to get length of linked list def Length(self): if not self.isEmpty(): prev_id = 0 node = self.head next_id = 1 count = 1 while next_id: next_id = prev_id ^ node.npx if next_id: prev_id = id(node) node = self.__type_cast(next_id) count += 1 else: return count else: return 0 # Function to print elements of the XOR Linked List def printMiddle(self, length): if self.head != None: prev_id = 0 node = self.head next_id = 1 # Traverse XOR linked list middle = length // 2 count = 0 prev = None while count != middle: count = count + 1 # Forward traversal next_id = prev_id ^ node.npx if next_id: # Update prev prev_id = id(node) # Update curr prev = node node = self.__type_cast(next_id) else: return if length % 2 != 0: print(node.value, end = ' ') else: print(prev.value, node.value, end = ' ') # method to check if the linked list is empty or not def isEmpty(self): if self.head is None: return True return False # method to return a new instance of type def __type_cast(self, id): return ctypes.cast(id, ctypes.py_object).value # Create following XOR Linked List# head-->40<-->30<-->20<-->10 head = XorLinkedList()head.insert(4)head.insert(7)head.insert(5)# Reverse the XOR Linked List to give# head-->10<-->20<-->30<-->40 length = head.Length()head.printMiddle(length)# This code is contributed by Nidhi goel. |
Javascript
// JavaScript program to implement the above approachclass Node { constructor(value) { this.value = value; this.npx = 0; }}// create linked list classclass XorLinkedList { // constructor constructor() { this.head = null; this.tail = null; this.__nodes = []; } // Function to insert a node with given value at given position insert(value) { // Initialize a new Node const node = new Node(value); // Check If XOR linked list is empty if (this.head === null) { // Update pointer of head node this.head = node; // Update pointer of tail node this.tail = node; } else { // Update curr node address this.head.npx = this.__getId(node) ^ this.head.npx; // Update new node address node.npx = this.__getId(this.head); // Update head this.head = node; } // push node this.__nodes.push(node); } // method to get length of linked list length() { if (!this.isEmpty()) { let prevId = 0; let node = this.head; let nextId = 1; let count = 1; while (nextId) { nextId = prevId ^ node.npx; if (nextId) { prevId = this.__getId(node); node = this.__typeCast(nextId); count += 1; } else { return count; } } } else { return 0; } } // Function to print elements of the XOR Linked List printMiddle(length) { if (this.head !== null) { let prevId = 0; let node = this.head; let nextId = 1; // Traverse XOR linked list const middle = Math.floor(length / 2); let count = 0; let prev = null; while (count !== middle) { count = count + 1; // Forward traversal nextId = prevId ^ node.npx; if (nextId) { // Update prev prevId = this.__getId(node); // Update curr prev = node; node = this.__typeCast(nextId); } else { return; } } if (length % 2 !== 0) { console.log(node.value); } else { console.log(prev.value, node.value); } } } // method to check if the linked list is empty or not isEmpty() { if (this.head === null) { return true; } return false; } // method to return a new instance of type __typeCast(id) { return ctypes.cast(id, ctypes.py_object).value; } // method to get the unique ID of an object __getId(obj) { return obj && obj.__unique_id__; }}// Create following XOR Linked List// head-->40<-->30<-->20<-->10const head = new XorLinkedList();head.insert(4);head.insert(5);head.insert(7);// Reverse the XOR Linked List to give// head-->10<-->20<-->30<-->40const length = head.length();head.printMiddle(length);//this is generated by chetanbargal |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
