Revertir iterativamente una lista enlazada usando solo 2 punteros (un método interesante)

Dado el puntero al Node principal de una lista enlazada, la tarea es invertir la lista enlazada.

Ejemplos: 

Input : Head of following linked list  
       1->2->3->4->NULL
Output : Linked list should be changed to,
       4->3->2->1->NULL

Input : Head of following linked list  
       1->2->3->4->5->NULL
Output : Linked list should be changed to,
       5->4->3->2->1->NULL

Hemos visto cómo invertir una lista enlazada en el artículo Invertir una lista enlazada . En el método iterativo habíamos usado 3 punteros prev, cur y next . A continuación se muestra un enfoque interesante que utiliza solo dos punteros. La idea es usar XOR para intercambiar punteros. 

Complete Interview Preparation - GFG

C++

// C++ program to reverse a linked list using two pointers.
#include <bits/stdc++.h>
using namespace std;
typedef uintptr_t ut;
  
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
  
/* Function to reverse the linked list using 2 pointers */
void reverse(struct Node** head_ref)
{
    struct Node* prev = NULL;
    struct Node* current = *head_ref;
  
    // at last prev points to new head
    while (current != NULL) {
        // This expression evaluates from left to right
        // current->next = prev, changes the link from
        // next to prev node
        // prev = current, moves prev to current node for
        // next reversal of node
        // This example of list will clear it more
        // 1->2->3->4 initially prev = 1, current = 2 Final
        // expression will be current = 1^2^3^2^1, as we
        // know that bitwise XOR of two same numbers will
        // always be 0 i.e; 1^1 = 2^2 = 0 After the
        // evaluation of expression current = 3 that means
        // it has been moved by one node from its previous
        // position
        current
            = (struct Node*)((ut)prev ^ (ut)current
                             ^ (ut)(current->next)
                             ^ (ut)(current->next = prev)
                             ^ (ut)(prev = current));
    }
  
    *head_ref = prev;
}
  
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
  
    /* put in the data  */
    new_node->data = new_data;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);
  
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
  
/* Function to print linked list */
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
  
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 85);
  
    printf("Given linked list\n");
    printList(head);
    reverse(&head);
    printf("\nReversed Linked list \n");
    printList(head);
    return 0;
}

Java

// Java program to reverse a linked
// list using two pointers.
import java.util.*;
  
class Main {
  
    // Link list node
    static class Node {
        int data;
        Node next;
    };
  
    static Node head_ref = null;
  
    // Function to reverse the linked
    // list using 2 pointers
    static void reverse()
    {
        Node prev = null;
        Node current = head_ref;
  
        // At last prev points to new head
        while (current != null) {
  
            // This expression evaluates from left to right
            // current.next = prev, changes the link from
            // next to prev node
            // prev = current, moves prev to current node
            // for next reversal of node This example of
            // list will clear it more 1.2.3.4 initially
            // prev = 1, current = 2 Final expression will
            // be current = 1^2^3^2^1, as we know that
            // bitwise XOR of two same numbers will always
            // be 0 i.e; 1^1 = 2^2 = 0 After the evaluation
            // of expression current = 3 that means it has
            // been moved by one node from its previous
            // position
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head_ref = prev;
    }
  
    // Function to push a node
    static void push(int new_data)
    {
  
        // Allocate node
        Node new_node = new Node();
  
        // Put in the data
        new_node.data = new_data;
  
        // Link the old list off the new node
        new_node.next = (head_ref);
  
        // Move the head to point to the new node
        (head_ref) = new_node;
    }
  
    // Function to print linked list
    static void printList()
    {
        Node temp = head_ref;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
  
    // Driver code
    public static void main(String[] args)
    {
        push(20);
        push(4);
        push(15);
        push(85);
  
        System.out.print("Given linked list\n");
        printList();
        reverse();
        System.out.print("\nReversed Linked list \n");
        printList();
    }
}
  
// This code is contributed by rutvik_56

Python3

# Iteratively Reverse a linked list using only 2 pointers (An Interesting Method)
# Python program to reverse a linked list
# Link list node
# node class
  
  
class node:
  
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None
  
  
class LinkedList:
  
    # Function to initialize head
    def __init__(self):
        self.head = None
  
    # Function to reverse the linked list
    def reverse(self):
        prev = None
        current = self.head
    # Described here https://www.geeksforgeeks.org/
    # how-to-swap-two-variables-in-one-line /
        while(current is not None):
            # This expression evaluates from left to right
            # current->next = prev, changes the link from
            # next to prev node
            # prev = current, moves prev to current node for
            # next reversal of node
            # This example of list will clear it more 1->2
            # initially prev = 1, current = 2
            # Final expression will be current = 1, prev = 2
            next, current.next = current.next, prev
            prev, current = current, next
        self.head = prev
  
    # Function to push a new node
    def push(self, new_data):
        # allocate node and put in the data
        new_node = node(new_data)
        # link the old list off the new node
        new_node.next = self.head
        # move the head to point to the new node
        self.head = new_node
  
    # Function to print the linked list
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data, end=" ")
            temp = temp.next
  
  
# Driver program to test above functions
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
  
print("Given Linked List")
llist.printList()
llist.reverse()
print("\nReversed Linked List")
llist.printList()
  
# This code is contributed by Afzal Ansari

C#

// C# program to reverse a linked
// list using two pointers.
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
  
    // Link list node
    class Node {
        public int data;
        public Node next;
    };
  
    static Node head_ref = null;
  
    // Function to reverse the linked
    // list using 2 pointers
    static void reverse()
    {
        Node prev = null;
        Node current = head_ref;
  
        // At last prev points to new head
        while (current != null) {
  
            // This expression evaluates from left to right
            // current.next = prev, changes the link from
            // next to prev node
            // prev = current, moves prev to current node
            // for next reversal of node This example of
            // list will clear it more 1.2.3.4 initially
            // prev = 1, current = 2 Final expression will
            // be current = 1^2^3^2^1, as we know that
            // bitwise XOR of two same numbers will always
            // be 0 i.e; 1^1 = 2^2 = 0 After the evaluation
            // of expression current = 3 that means it has
            // been moved by one node from its previous
            // position
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head_ref = prev;
    }
  
    // Function to push a node
    static void push(int new_data)
    {
  
        // Allocate node
        Node new_node = new Node();
  
        // Put in the data
        new_node.data = new_data;
  
        // Link the old list off the new node
        new_node.next = (head_ref);
  
        // Move the head to point to the new node
        (head_ref) = new_node;
    }
  
    // Function to print linked list
    static void printList()
    {
        Node temp = head_ref;
        while (temp != null) {
            Console.Write(temp.data + " ");
            temp = temp.next;
        }
    }
  
    // Driver code
    public static void Main(string[] args)
    {
        push(20);
        push(4);
        push(15);
        push(85);
  
        Console.Write("Given linked list\n");
        printList();
        reverse();
        Console.Write("\nReversed Linked list \n");
        printList();
    }
}
  
// This code is contributed by pratham76

Javascript

<script>
// javascript program to reverse a linked 
// list using two pointers.
  
    // Link list node
class Node 
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
}
  
    var head_ref = null;
  
    // Function to reverse the linked
    // list using 2 pointers
    function reverse()
    {
        var prev = null;
        var current = head_ref;
  
        // At last prev points to new head
        while (current != null)
        {
  
            // This expression evaluates from left to right
            // current.next = prev, changes the link from
            // next to prev node
            // prev = current, moves prev to current node for
            // next reversal of node
            // This example of list will clear it more 1.2.3.4
            // initially prev = 1, current = 2
            // Final expression will be current = 1^2^3^2^1,
            // as we know that bitwise XOR of two same
            // numbers will always be 0 i.e; 1^1 = 2^2 = 0
            // After the evaluation of expression current = 3 that
            // means it has been moved by one node from its
            // previous position
            var next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head_ref = prev;
    }
  
    // Function to push a node
    function push(new_data)
    {
  
        // Allocate node
        var new_node = new Node();
  
        // Put in the data
        new_node.data = new_data;
  
        // Link the old list off the new node
        new_node.next = (head_ref);
  
        // Move the head to point to the new node
        (head_ref) = new_node;
    }
  
    // Function to print linked list
    function printList()
    {
        var temp = head_ref;
        while (temp != null)
        {
            document.write(temp.data + " ");
            temp = temp.next;
        }
    }
  
    // Driver code    
        push(20);
        push(4);
        push(15);
        push(85);
  
        document.write("Given linked list<br/>");
        printList();
        reverse();
        document.write("<br/>Reversed Linked list <br/>");
        printList();
  
// This code is contributed by todaysgaurav. 
</script>
Producción: 

Given linked list
85  15  4  20  
Reversed Linked list 
20  4  15  85

 

Complejidad de tiempo: O(n) 
Espacio auxiliar: O(1) ya que usa espacio para anterior y siguiente

Solución alternativa: 

C++

// C++ program to reverse a linked list using two pointers.
#include <bits/stdc++.h>
using namespace std;
typedef uintptr_t ut;
  
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
  
/* Function to reverse the linked list using 2 pointers */
void reverse(struct Node** head_ref)
{
    struct Node* current = *head_ref;
    struct Node* next;
    while (current->next != NULL) {
        next = current->next;
        current->next = next->next;
        next->next = (*head_ref);
        *head_ref = next;
    }
}
  
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
  
/* Function to print linked list */
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
  
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 85);
  
    printf("Given linked list\n");
    printList(head);
    reverse(&head);
    printf("\nReversed Linked list \n");
    printList(head);
    return 0;
}

Java

// Java program to reverse a linked
// list using two pointers.
import java.util.*;
  
class Main {
  
    // Link list node
    static class Node {
        int data;
        Node next;
    };
  
    static Node head_ref = null;
  
    // Function to reverse the linked
    // list using 2 pointers
    static void reverse()
    {
        Node next;
        Node curr = head_ref;
        while (curr.next != null) {
            next = curr.next;
            curr.next = next.next;
            next.next = head_ref;
            head_ref = next;
        }
    }
  
    // Function to push a node
    static void push(int new_data)
    {
  
        // Allocate node
        Node new_node = new Node();
  
        // Put in the data
        new_node.data = new_data;
  
        // Link the old list off the new node
        new_node.next = (head_ref);
  
        // Move the head to point to the new node
        (head_ref) = new_node;
    }
  
    // Function to print linked list
    static void printList()
    {
        Node temp = head_ref;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
  
    // Driver code
    public static void main(String[] args)
    {
        push(20);
        push(4);
        push(15);
        push(85);
  
        System.out.print("Given linked list\n");
        printList();
        reverse();
        System.out.print("\nReversed Linked list \n");
        printList();
    }
}
  
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Python3

# Python3 program to reverse a linked list using two pointers.
  
# A linked list node 
class Node :
    def __init__(self):
        self.data = 0
        self.next = None
  
# Function to reverse the linked list using 2 pointers 
def reverse(head_ref):
  
    current = head_ref
    next= None
    while (current.next != None) :
        next = current.next
        current.next = next.next
        next.next = (head_ref)
        head_ref = next
      
    return head_ref
  
# Function to push a node 
def push( head_ref, new_data):
  
    new_node = Node()
    new_node.data = new_data
    new_node.next = (head_ref)
    (head_ref) = new_node
    return head_ref
  
# Function to print linked list 
def printList( head):
  
    temp = head
    while (temp != None) :
        print( temp.data, end=" ")
        temp = temp.next
      
# Driver code
  
# Start with the empty list 
head = None
  
head = push(head, 20)
head = push(head, 4)
head = push(head, 15)
head = push(head, 85)
  
print("Given linked list")
printList(head)
head = reverse(head)
print("\nReversed Linked list ")
printList(head)
  
# This code is contributed by Arnab Kundu

C#

// C# program to reverse a linked
// list using two pointers.
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
  
    // Link list node
    class Node {
        public int data;
        public Node next;
    };
  
    static Node head_ref = null;
  
    // Function to reverse the linked
    // list using 2 pointers
    static void reverse()
    {
        Node current = head_ref;
        Node next;
        while (current.next != null) {
            next = current.next;
            current.next = next.next;
            next.next = head_ref;
            head_ref = next;
        }
    }
  
    // Function to push a node
    static void push(int new_data)
    {
  
        // Allocate node
        Node new_node = new Node();
  
        // Put in the data
        new_node.data = new_data;
  
        // Link the old list off the new node
        new_node.next = (head_ref);
  
        // Move the head to point to the new node
        (head_ref) = new_node;
    }
  
    // Function to print linked list
    static void printList()
    {
        Node temp = head_ref;
        while (temp != null) {
            Console.Write(temp.data + " ");
            temp = temp.next;
        }
    }
  
    // Driver code
    public static void Main(string[] args)
    {
        push(20);
        push(4);
        push(15);
        push(85);
  
        Console.Write("Given linked list\n");
        printList();
        reverse();
        Console.Write("\nReversed Linked list \n");
        printList();
    }
}
  
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Javascript

<script>
// javascript program to reverse a linked 
// list using two pointers.
  
    // Link list node
class Node 
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
}
  
    var head_ref = null;
  
    // Function to reverse the linked
    // list using 2 pointers
    function reverse()
    {
        var current = head_ref;
        var next;
        while (current.next != null)
        {
            next = current.next;
            current.next = next.next;
            next.next = head_ref;
            head_ref = next;
        }
    }
  
    // Function to push a node
    function push(new_data)
    {
  
        // Allocate node
        var new_node = new Node();
  
        // Put in the data
        new_node.data = new_data;
  
        // Link the old list off the new node
        new_node.next = (head_ref);
  
        // Move the head to point to the new node
        (head_ref) = new_node;
    }
  
    // Function to print linked list
    function printList()
    {
        var temp = head_ref;
        while (temp != null)
        {
            document.write(temp.data + " ");
            temp = temp.next;
        }
    }
  
    // Driver code    
        push(20);
        push(4);
        push(15);
        push(85);
  
        document.write("Given linked list<br/>");
        printList();
        reverse();
        document.write("<br/>Reversed Linked list <br/>");
        printList();
  
// This code is contributed by Abhijeet Kumar(abhijeet19403) 
</script>
Producción: 

Given linked list
85  15  4  20  
Reversed Linked list 
20  4  15  85

 

Complejidad temporal : O(n) 
Espacio auxiliar: O(1)

Gracias a Abhay Yadav por sugerir este enfoque.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *