Lista enlazada XOR: inversión de una lista

Posted on by Rudeus Greyrat

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:

  1. Inicialice una variable de puntero, digamos curr , para apuntar al Node actual que se está atravesando.
  2. Almacene el puntero de cabeza actual en la variable curr .
  3. Si curr es igual a NULL , devuelve NULL .
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *