Dada una lista enlazada XOR y la posición y el valor de dos enteros , la tarea es insertar un Node que contenga valor como la posición del Node XOR de la lista enlazada XOR .
Ejemplos :
Entrada: 4<–>7<–>9<–>7, posición = 3, valor = 6
Salida: 4<–>7<–>6<–>9<–>7
Explicación:
Insertar un Node en el 3 La tercera posición con valor 6 modifica la lista enlazada XOR dada a 4<–>7<–>6<–>9<–>7.Entrada: 4<–>7<–>9<–>7, posición=6, valor=6
Salida: Posición no válida
Explicación: Dado que la lista dada consta de solo 4 elementos, la 6.ª posición es una posición no válida en la lista dada.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, diga ctr para mantener un recuento de los Nodes atravesados en la lista vinculada XOR dada.
- Atraviesa la lista enlazada XOR dada . Para cada Node de la lista enlazada XOR, verifique si la posición del Node actual es igual a la posición o no. Si se encuentra que es cierto, inserte el Node en la lista vinculada XOR dada.
- De lo contrario, incremente ctr en 1 .
- Si se recorre toda la lista y no se obtuvo la posición del Node, imprima “ Posición no válida” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include<bits/stdc++.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, int position) { // If XOR linked list is empty if (*head == NULL) { // If given position // is equal to 1 if (position == 1) { // 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 required position was not found else { cout << "Invalid Position\n"; } } // If the XOR linked list // is not empty else { // Stores position of a node // in the XOR linked list int Pos = 1; // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // Stores the XOR of next // node and previous node struct Node* next = XOR(prev, curr->nxp); // Traverse the XOR linked list while (next != NULL && Pos < position - 1) { // Update prev prev = curr; // Update curr curr = next; // Update next next = XOR(prev, curr->nxp); // Update Pos Pos++; } // If the position of the current // node is equal to the given position if (Pos == position - 1) { // Initialize a new Node struct Node* node = new Node(); // Stores pointer to previous Node // as (prev ^ next ^ next) = prev struct Node* temp = XOR(curr->nxp, next); // Stores XOR of prev and new node curr->nxp = XOR(temp, node); // Connecting new node with next if (next != NULL) { // Update pointer of next next->nxp = XOR(node, XOR(next->nxp, curr)); } // Connect node with curr and // next curr<--node-->next node->nxp = XOR(curr, next); node->data = value; } // Insertion node at beginning else if (position == 1) { // 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; } else { cout << "Invalid Position\n"; } } 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; } } // Driver Code int main() { /* Create following XOR Linked List head-->20<-->40<-->10<-->30 */ struct Node* head = NULL; insert(&head, 10, 1); insert(&head, 20, 1); insert(&head, 30, 3); insert(&head, 40, 2); // Print the new list printList(&head); 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, int position) { // If XOR linked list is empty if (*head == NULL) { // If given position // is equal to 1 if (position == 1) { // 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 required position was not found else { printf("Invalid Position\n"); } } // If the XOR linked list // is not empty else { // Stores position of a node // in the XOR linked list int Pos = 1; // Stores the address // of current node struct Node* curr = *head; // Stores the address // of previous node struct Node* prev = NULL; // Stores the XOR of next // node and previous node struct Node* next = XOR(prev, curr->nxp); // Traverse the XOR linked list while (next != NULL && Pos < position - 1) { // Update prev prev = curr; // Update curr curr = next; // Update next next = XOR(prev, curr->nxp); // Update Pos Pos++; } // If the position of the current // node is equal to the given position if (Pos == position - 1) { // Initialize a new Node struct Node* node = (struct Node*)malloc( sizeof(struct Node)); // Stores pointer to previous Node // as (prev ^ next ^ next) = prev struct Node* temp = XOR(curr->nxp, next); // Stores XOR of prev and new node curr->nxp = XOR(temp, node); // Connecting new node with next if (next != NULL) { // Update pointer of next next->nxp = XOR(node, XOR(next->nxp, curr)); } // Connect node with curr and // next curr<--node-->next node->nxp = XOR(curr, next); node->data = value; } // Insertion node at beginning else if (position == 1) { // 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; } else { printf("Invalid Position\n"); } } 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; } } // Driver Code int main() { /* Create following XOR Linked List head-->20<-->40<-->10<-->30 */ struct Node* head = NULL; insert(&head, 10, 1); insert(&head, 20, 1); insert(&head, 30, 3); insert(&head, 40, 2); // Print the new list printList(&head); return (0); }
20 40 10 30
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por debarpan_bose_chowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA