Given a XOR linked list and an integer N, the task is to print the Nth node from the end of the given XOR linked list.
Examples:
Input: 4 –> 6 –> 7 –> 3, N = 1
Output: 3
Explanation: 1st node from the end is 3.
Input: 5 –> 8 –> 9, N = 4
Output: Wrong Input
Explanation: The given Xor Linked List contains only 3 nodes.
Approach: Follow the steps below to solve the problem:
- Traverse the first N nodes of the Linked List using a pointer, say curr.
- Use another pointer, say curr1, and traverse the linked list incrementing curr and curr1 by a node after every iteration.
- Iterate until the pointer curr exceeds the end of the List, i.e.NULL. Once reached, print the value of the node curr1 as the required answer.
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 list struct 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 nodes struct 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 position struct 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 elements of // the XOR Linked List void printList( struct Node** head) { // 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; // Traverse XOR linked list while (curr != NULL) { // Print current node cout << curr->data << " " ; // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; } } struct Node* NthNode( struct Node** head, int N) { int count = 0; // Stores XOR pointer // in current node struct Node* curr = *head; struct Node* curr1 = *head; // Stores XOR pointer of // in previous Node struct Node* prev = NULL; struct Node* prev1 = NULL; // Stores XOR pointer of // in next node struct Node* next; struct Node* next1; while (count < N && curr != NULL) { // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; count++; } if (curr == NULL && count < N) { cout << "Wrong Input\n" ; return ( uintptr_t )0; } else { while (curr != NULL) { // Forward traversal next = XOR(prev, curr->nxp); next1 = XOR(prev1, curr1->nxp); // Update prev prev = curr; prev1 = curr1; // Update curr curr = next; curr1 = next1; } cout << curr1->data << " " ; } } // Driver Code int main() { /* Create following XOR Linked List head -->7 –> 6 –>8 –> 11 –> 3 –> 1 –> 2 –> 0*/ struct Node* head = NULL; insert(&head, 0); insert(&head, 2); insert(&head, 1); insert(&head, 3); insert(&head, 11); insert(&head, 8); insert(&head, 6); insert(&head, 7); NthNode(&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 list struct 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 nodes struct 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 position struct 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 elements of // the XOR Linked List void printList( struct Node** head) { // 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; // Traverse XOR linked list while (curr != NULL) { // Print current node printf ( "%d " , curr->data); // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; } } struct Node* NthNode( struct Node** head, int N) { int count = 0; // Stores XOR pointer // in current node struct Node* curr = *head; struct Node* curr1 = *head; // Stores XOR pointer of // in previous Node struct Node* prev = NULL; struct Node* prev1 = NULL; // Stores XOR pointer of // in next node struct Node* next; struct Node* next1; while (count < N && curr != NULL) { // Forward traversal next = XOR(prev, curr->nxp); // Update prev prev = curr; // Update curr curr = next; count++; } if (curr == NULL && count < N) { printf ( "Wrong Input" ); return ( uintptr_t )0; } else { while (curr != NULL) { // Forward traversal next = XOR(prev, curr->nxp); next1 = XOR(prev1, curr1->nxp); // Update prev prev = curr; prev1 = curr1; // Update curr curr = next; curr1 = next1; } printf ( "%d" , curr1->data); } } // Driver Code int main() { /* Create following XOR Linked List head -->7 –> 6 –>8 –> 11 –> 3 –> 1 –> 2 –> 0*/ struct Node* head = NULL; insert(&head, 0); insert(&head, 2); insert(&head, 1); insert(&head, 3); insert(&head, 11); insert(&head, 8); insert(&head, 6); insert(&head, 7); NthNode(&head, 3); return (0); } |
Python3
# Python implementation of the above approach. import ctypes # Structure of a node in XOR linked list class Node: def __init__( self , value): self .value = value self .npx = 0 # create linked list class class 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 def NthNode( self , N): count = 1 # Stores XOR pointer of # in previous Node prev_id = 0 prev1_id = 0 # Stores XOR pointer # in current node node = self .head node1 = self .head # Stores XOR pointer of # in next node next_id = 1 next1_id = 1 while (next_id and count < N): # Forward traversal next_id = prev_id ^ node.npx if next_id: # Update prev prev_id = id (node) # Update curr node = self .__type_cast(next_id) count = count + 1 # Move 1 step forward because in python, prev1_id and next1_id are # starting from 0 and 1 respectively, and not with None. next_id = prev_id ^ node.npx prev_id = id (node) node = self .__type_cast(next_id) if not next_id and count < N: print ( "Wrong Input" ) return while next_id: # Forward Traversal next_id = prev_id ^ node.npx next1_id = prev1_id ^ node1.npx # Update prev if next_id: prev_id = id (node) node = self .__type_cast(next_id) # Update curr if next_id: prev1_id = id (node1) node1 = self .__type_cast(next1_id) node1 = self .__type_cast(next1_id) print (node1.value) # Function to print elements of the XOR Linked List def printList( self ): if self .head ! = None : prev_id = 0 node = self .head next_id = 1 print (node.value, end = ' ' ) # Traverse XOR linked list while next_id: # Forward traversal next_id = prev_id ^ node.npx if next_id: # Update prev prev_id = id (node) # Update curr node = self .__type_cast(next_id) # Print current node print (node.value, end = ' ' ) else : return # 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 -->7 –> 6 –>8 –> 11 –> 3 –> 1 –> 2 –> 0 head = XorLinkedList() head.insert( 0 ) head.insert( 2 ) head.insert( 1 ) head.insert( 3 ) head.insert( 11 ) head.insert( 8 ) head.insert( 6 ) head.insert( 7 ) head.NthNode( 3 ) # This code is contributed by Nidhi goel. |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!