Lista vinculada XOR: busque el enésimo Node desde el final

Dada una lista enlazada XOR y un número entero N , la tarea es imprimir el Node N desde el final de la lista enlazada XOR dada .

Ejemplos:

Entrada: 4 –> 6 –> 7 –> 3, N = 1 
Salida:
Explicación: el primer Node desde el final es 3.
Entrada: 5 –> 8 –> 9, N = 4 
Salida: Entrada incorrecta 
Explicación: El dado Xor Linked List contiene solo 3 Nodes. 
 

Enfoque: siga los pasos a continuación para resolver el problema:

  • Recorra los primeros N Nodes de la lista enlazada usando un puntero, digamos curr .
  • Use otro puntero, digamos curr1 , y recorra la lista enlazada incrementando curr y curr1 por un Node después de cada iteración.
  • Iterar hasta que el puntero actual exceda el final de la Lista, es decir, NULL . Una vez alcanzado, imprima el valor del Node curr1 como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

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);
}
Producción: 

1

 

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 *