Convertir lista enlazada individualmente a lista enlazada XOR

requisito previo
 

Una lista enlazada XOR es una lista doblemente enlazada eficiente en memoria en la que el siguiente puntero de cada Node almacena el XOR de la dirección del Node anterior y siguiente. 
Dada una lista enlazada individualmente, la tarea es convertir la lista individual dada en una lista enlazada XOR.
 

Enfoque : dado que en la lista vinculada XOR , cada puntero siguiente almacena el XOR de la dirección de los Nodes anterior y siguiente . Entonces, la idea es recorrer la lista de enlaces individuales dada y realizar un seguimiento del Node anterior en un puntero, por ejemplo, prev .
Ahora, mientras recorre la lista, cambie el siguiente puntero de cada Node como: 
 

current -> next = XOR(prev, current->next)

Imprimiendo la lista enlazada XOR
mientras imprimimos la lista enlazada XOR, tenemos que encontrar la dirección exacta del siguiente Node cada vez. Como hemos visto anteriormente, el siguiente puntero de cada Node almacena el valor XOR de la dirección del Node anterior y siguiente. Por lo tanto, la dirección del siguiente Node se puede obtener encontrando el XOR de los punteros anterior y siguiente del Node actual en la lista enlazada de XOR.
Por lo tanto, para imprimir la lista enlazada XOR, revísela manteniendo un puntero anterior que almacena la dirección del Node anterior y para encontrar el siguiente Node, calcule XOR de anterior con el siguiente del Node actual.
A continuación se muestra la implementación del enfoque anterior: 
 

CPP

// C++ program to Convert a Singly Linked
// List to XOR Linked List
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Linked List node
struct Node {
    int data;
    struct Node* next;
};
 
// Utility function to create new node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
 
    return temp;
}
 
// Print singly linked list before conversion
void print(Node* head)
{
    while (head) {
 
        // print current node
        cout << head->data << " ";
        head = head->next;
    }
 
    cout << endl;
}
 
// Function to find XORed value of
// the node addresses
Node* XOR(Node* a, Node* b)
{
    return (Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}
 
// Function to convert singly linked
// list to XOR linked list
void convert(Node* head)
{
    Node* curr = head;
    Node* prev = NULL;
    Node* next = curr->next;
 
    while (curr) {
 
        // store curr->next in next
        next = curr->next;
 
        // change curr->next to XOR of prev and next
        curr->next = XOR(prev, next);
 
        // prev will change to curr for next iteration
        prev = curr;
 
        // curr is now pointing to next for next iteration
        curr = next;
    }
}
 
// Function to print XORed linked list
void printXOR(Node* head)
{
    Node* curr = head;
    Node* prev = NULL;
 
    while (curr) {
 
        // print current node
        cout << curr->data << " ";
 
        Node* temp = curr;
 
        /* compute curr as prev^curr->next as
           it is previously set as prev^curr->next so
           this time curr would be prev^prev^curr->next
           which is curr->next */
        curr = XOR(prev, curr->next);
 
        prev = temp;
    }
 
    cout << endl;
}
 
// Driver Code
int main()
{
    // Create following singly linked list
    // 1->2->3->4
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
 
    cout << "Before Conversion : " << endl;
    print(head);
 
    convert(head);
    cout << "After Conversion : " << endl;
    printXOR(head);
 
    return 0;
}

Java

// Java program to Convert a Singly Linked
// List to XOR Linked List
import java.io.*;
 
// Linked List node
class Node
{
    int data;
    Node next;
    
    // Utility function to create new node
    Node(int item)
    {
        data = item;
        next = null;
    }
}
class GFG
{
    public static Node root;
   
    // Print singly linked list before conversion
    static void print(Node head)
    {
        while (head != null)
        {
           
            // print current node
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }
   
    // Function to find XORed value of
    // the node addresses
    static Node XOR(Node a, Node b)
    {
        return b;
    }
   
    // Function to convert singly linked
    // list to XOR linked list
    static void convert(Node head)
    {
        Node curr = head;
        Node prev = null;
        Node next = curr.next;
         
        while(curr != null)
        {
           
            // store curr->next in next
            next = curr.next;
             
            // change curr->next to XOR of prev and next
            curr.next = XOR(prev, next);
             
            // prev will change to curr for next iteration
            prev = curr;
             
            // curr is now pointing to next for next iteration
            curr = next;
        }
    }
   
    // Function to print XORed linked list
    static void printXOR(Node head)
    {
        Node curr = head;
        Node prev = null;
        while(curr != null)
        {
           
            // print current node
            System.out.print(curr.data + " ");
            Node temp = curr;
             
            /* compute curr as prev^curr->next as
           it is previously set as prev^curr->next so
           this time curr would be prev^prev^curr->next
           which is curr->next */
            curr = XOR(prev, curr.next);
            prev = temp;
        }
        System.out.println();
    }
   
    // Driver Code
    public static void main (String[] args)
    {
       
        // Create following singly linked list
        // 1->2->3->4
        GFG tree = new GFG();
        tree.root = new Node(1);
        tree.root.next = new Node(2);
        tree.root.next.next = new Node(3);
        tree.root.next.next.next = new Node(4);     
        System.out.println("Before Conversion : ");
        print(root);
        convert(root);
        System.out.println("After Conversion : ");
        printXOR(root);
    }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 program to Convert a Singly Linked
# List to XOR Linked List
 
# Linked List node
class Node:
    def __init__(self,d):
        self.data = d
        self.next = None
 
# Print singly linked list before conversion
def printt(head):
    while (head):
 
        # print current node
        print(head.data, end=" ")
        head = head.next
    print()
 
# Function to find XORed value of
# the node addresses
def XOR(a, b):
    return b
 
# Function to convert singly linked
# list to XOR linked list
def convert(head):
    curr = head
    prev = None
    next = curr.next
 
    while (curr):
 
        # store curr.next in next
        next = curr.next
 
        # change curr.next to XOR of prev and next
        curr.next = XOR(prev, next)
 
        # prev will change to curr for next iteration
        prev = curr
 
        # curr is now pointing to next for next iteration
        curr = next
 
# Function to print XORed linked list
def printXOR(head):
    curr = head
    prev = None
 
    while (curr):
 
        # print current node
        print(curr.data, end=" ")
 
        temp = curr
 
        # /* compute curr as prev^curr.next as
        #    it is previously set as prev^curr.next so
        #    this time curr would be prev^prev^curr.next
        #    which is curr.next */
        curr = XOR(prev, curr.next)
 
        prev = temp
 
    print()
 
# Driver Code
if __name__ == '__main__':
     
    # Create following singly linked list
    # 1.2.3.4
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
 
    print("Before Conversion : ")
    printt(head)
 
    convert(head)
    print("After Conversion : ")
    printXOR(head)
 
# This code is contributed by mohitkumar29

C#

using System;
class Node
{
    public int data;
    public Node next;
     
    // Utility function to create new node
    public Node(int item)
    {
        data = item;
        next = null;
    }
}
 
public class GFG
{
    static Node root;
   
    // Print singly linked list before conversion
    static void print(Node head)
    {
        while (head != null)
        {
            
            // print current node
            Console.Write(head.data + " ");
            head = head.next;
        }
        Console.WriteLine();
    }
   
    // Function to find XORed value of
    // the node addresses
    static Node XOR(Node a, Node b)
    {
        return b;
    }
     
    // Function to convert singly linked
    // list to XOR linked list
    static void convert(Node head)
    {
        Node curr = head;
        Node prev = null;
        Node next = curr.next;       
        while(curr != null)
        {
            
            // store curr->next in next
            next = curr.next;
              
            // change curr->next to XOR of prev and next
            curr.next = XOR(prev, next);
              
            // prev will change to curr for next iteration
            prev = curr;
              
            // curr is now pointing to next for next iteration
            curr = next;
        }
    }
     
    // Function to print XORed linked list
    static void printXOR(Node head)
    {
        Node curr = head;
        Node prev = null;
        while(curr != null)
        {
            
            // print current node
            Console.Write(curr.data + " ");
            Node temp = curr;
              
            /* compute curr as prev^curr->next as
           it is previously set as prev^curr->next so
           this time curr would be prev^prev^curr->next
           which is curr->next */
            curr = XOR(prev, curr.next);
            prev = temp;
        }
        Console.WriteLine();
    }
     
    // Driver Code
    static public void Main ()
    {
       
        // Create following singly linked list
        // 1->2->3->4
        GFG.root = new Node(1);
        GFG.root.next = new Node(2);
        GFG.root.next.next = new Node(3);
        GFG.root.next.next.next = new Node(4);     
         
        Console.WriteLine("Before Conversion : ");
        print(root);
        convert(root);
        Console.WriteLine("After Conversion : ");
        printXOR(root);
    }
}
 
// This code is contributed by rag2127

Javascript

<script>
// javascript program to Convert a Singly Linked
// List to XOR Linked List// Linked List node
class Node {
 
    // Utility function to create new node
    constructor(val) {
        this.data = val;
        this.next = null;
    }
}
var root;
 
    // Print singly linked list before conversion
    function print( head) {
        while (head != null) {
 
            // print current node
            document.write(head.data + " ");
            head = head.next;
        }
        document.write("<br/>");
    }
 
    // Function to find XORed value of
    // the node addresses
    function XOR( a,  b) {
        return b;
    }
 
    // Function to convert singly linked
    // list to XOR linked list
    function convert( head) {
        var curr = head;
        var prev = null;
        var next = curr.next;
 
        while (curr != null) {
 
            // store curr->next in next
            next = curr.next;
 
            // change curr->next to XOR of prev and next
            curr.next = XOR(prev, next);
 
            // prev will change to curr for next iteration
            prev = curr;
 
            // curr is now pointing to next for next iteration
            curr = next;
        }
    }
 
    // Function to print XORed linked list
    function printXOR( head) {
        var curr = head;
        var prev = null;
        while (curr != null) {
 
            // print current node
            document.write(curr.data + " ");
            var temp = curr;
 
            /*
             * compute curr as prev^curr->next as it is previously set as prev^curr->next so
             * this time curr would be prev^prev^curr->next which is curr->next
             */
            curr = XOR(prev, curr.next);
            prev = temp;
        }
        document.write();
    }
 
    // Driver Code
     
 
        // Create following singly linked list
        // 1->2->3->4
     
        root = new Node(1);
        root.next = new Node(2);
        root.next.next = new Node(3);
        root.next.next.next = new Node(4);
        document.write("Before Conversion : <br/>");
        print(root);
        convert(root);
        document.write("After Conversion : <br/>");
        printXOR(root);
 
// This code contributed by gauravrajput1
</script>
Producción: 

Before Conversion : 
1 2 3 4 
After Conversion : 
1 2 3 4

 

Publicación traducida automáticamente

Artículo escrito por Poojaa Baliyan 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 *