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.
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