Dada una lista enlazada XOR , la tarea es invertir la lista enlazada XOR.
Ejemplos:
Entrada: 4 <–> 7 <–> 9 <–> 7
Salida: 7 <–> 9 <–> 7 <–> 4
Explicación:
Al invertir la lista vinculada, se modifica la lista vinculada XOR a 7 <–> 9 <–> 7 <–> 4.Entrada: 2 <-> 5 <-> 7 <-> 4
Salida: 4 <-> 7 <-> 5 <-> 2
Explicación:
Al invertir la lista vinculada, se modifica la lista vinculada XOR a 4 <-> 7 <-> 5 <-> 2.
Enfoque: la lista vinculada XOR consta de un solo puntero, que es el único puntero necesario para atravesar la lista vinculada XOR en ambas direcciones. Por lo tanto, la idea de resolver este problema es solo hacer que el último Node de la lista enlazada XOR sea su Head Node . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable de puntero, digamos curr , para apuntar al Node actual que se está atravesando.
- Almacene el puntero de cabeza actual en la variable curr .
- Si curr es igual a NULL , devuelve NULL .
- De lo contrario, recorra hasta el último Node y conviértalo en el encabezado de la lista enlazada XOR .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for 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
Node* nxp;
};
// Function to find the XOR of two nodes
Node* XOR(Node* a, Node* b)
{
return (Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}
// Function to insert a node with
// given value at beginning position
Node* insert(Node** head, int value)
{
// If XOR linked list is empty
if (*head == NULL)
{
// Initialize a new Node
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
Node* curr = *head;
// Stores the address
// of previous node
Node* prev = NULL;
// Initialize a new Node
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(Node** head)
{
// Stores XOR pointer
// in current node
Node* curr = *head;
// Stores XOR pointer of
// in previous Node
Node* prev = NULL;
// Stores XOR pointer of
// in next node
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;
}
cout << endl;
}
// Function to reverse the XOR linked list
Node* reverse(Node** head)
{
// Stores XOR pointer
// in current node
Node* curr = *head;
if (curr == NULL)
return NULL;
else
{
// Stores XOR pointer of
// in previous Node
Node* prev = NULL;
// Stores XOR pointer of
// in next node
Node* next;
while (XOR(prev, curr->nxp) != NULL)
{
// Forward traversal
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
}
// Update the head pointer
*head = curr;
return *head;
}
}
// Driver Code
int main()
{
/* Create following XOR Linked List
head-->40<-->30<-->20<-->10 */
Node* head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
/* Reverse the XOR Linked List to give
head-->10<-->20<-->30<-->40 */
cout << "XOR linked list: ";
printList(&head);
reverse(&head);
cout << "Reversed XOR linked list: ";
printList(&head);
return 0;
}
// This code is contributed by rutvik_56.
C
// C program for 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 beginning 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;
}
printf("\n");
}
// Function to reverse the XOR linked list
struct Node* reverse(struct Node** head)
{
// Stores XOR pointer
// in current node
struct Node* curr = *head;
if (curr == NULL)
return NULL;
else {
// Stores XOR pointer of
// in previous Node
struct Node* prev = NULL;
// Stores XOR pointer of
// in next node
struct Node* next;
while (XOR(prev, curr->nxp) != NULL) {
// Forward traversal
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
}
// Update the head pointer
*head = curr;
return *head;
}
}
// Driver Code
int main()
{
/* Create following XOR Linked List
head-->40<-->30<-->20<-->10 */
struct Node* head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
/* Reverse the XOR Linked List to give
head-->10<-->20<-->30<-->40 */
printf("XOR linked list: ");
printList(&head);
reverse(&head);
printf("Reversed XOR linked list: ");
printList(&head);
return (0);
}
Producción:
XOR linked list: 40 30 20 10 Reversed XOR linked list: 10 20 30 40
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