Dada una lista doblemente enlazada, se nos pide que invirtamos la lista en su lugar sin usar ningún espacio adicional.
Ejemplos:
Input : 1 <--> 2 <--> 5 <--> 6 <--> 7 Output : 7 <--> 6 <--> 5 <--> 2 <--> 1 Input : 11 <--> 22 <--> 33 <--> 22 <--> 1 Output : 1 <--> 22 <--> 33 <--> 22 <--> 11
Hemos discutido tres métodos para revertir una lista doblemente enlazada: Revertir una lista doblemente enlazada , Revertir una lista doblemente enlazada (Conjunto 2) e Revertir una lista doblemente enlazada usando recursividad .
Los dos primeros métodos funcionan en tiempo O(n) y no requieren espacio adicional. El primer método funciona intercambiando los punteros siguiente y anterior de cada Node. El segundo método toma cada Node de la lista y lo agrega al principio de la lista.
Hay otro enfoque que es un poco más intuitivo, pero también un poco más costoso.
Este método es similar a la array inversa. Para invertir una array, colocamos dos punteros, uno al principio y otro al final de la lista. Luego intercambiamos los datos de los dos punteros y avanzamos ambos punteros uno hacia el otro. Nos detenemos cuando los dos punteros se encuentran o cuando se cruzan. Realizamos exactamente n/2 intercambios, y la complejidad del tiempo también es O(N).
Una lista doblemente enlazada tiene un puntero anterior y otro siguiente, lo que significa que podemos recorrer la lista tanto hacia adelante como hacia atrás. Entonces, si colocamos un puntero (por ejemplo, el puntero izquierdo) al principio de la lista y otro puntero derecho al final de la lista, podemos acercar estos punteros haciendo avanzar el puntero izquierdo y retrocediendo el puntero derecho.
Algoritmo:
Step 1: Set LEFT to head of list
Step 2: Traverse the list and set RIGHT to end of the list
Step 3: Repeat following steps while LEFT != RIGHT and
LEFT->PREV != RIGHT
Step 4: Swap LEFT->DATA and RIGHT->DATA
Step 5: Advance LEFT pointer by one, LEFT = LEFT->NEXT
Step 6: Recede RIGHT pointer by one, i.e RIGHT = RIGHT->PREV
[END OF LOOP]
Step 7: End
Una nota sobre la eficiencia comparativa de los tres métodos
Algunas cosas deben ser mencionadas. Este método es simple de implementar, pero también es más costoso en comparación con el método de intercambio de punteros. Esto se debe a que intercambiamos datos y no punteros. El intercambio de datos puede resultar más costoso si los Nodes son tipos de datos grandes y complejos con varios miembros de datos. Por el contrario, el puntero al Node siempre será un tipo de datos más simple y de 4 u 8 bytes.
A continuación se muestra la implementación del algoritmo.
C++
// Cpp Program to Reverse a List using Data Swapping
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *prev, *next;
};
Node* newNode(int val)
{
Node* temp = new Node;
temp->data = val;
temp->prev = temp->next = nullptr;
return temp;
}
void printList(Node* head)
{
while (head->next != nullptr) {
cout << head->data << " <--> ";
head = head->next;
}
cout << head->data << endl;
}
// Insert a new node at the head of the list
void insert(Node** head, int val)
{
Node* temp = newNode(val);
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
// Function to reverse the list
void reverseList(Node** head)
{
Node* left = *head, * right = *head;
// Traverse the list and set right pointer to
// end of list
while (right->next != nullptr)
right = right->next;
// Swap data of left and right pointer and move
// them towards each other until they meet or
// cross each other
while (left != right && left->prev != right) {
// Swap data of left and right pointer
swap(left->data, right->data);
// Advance left pointer
left = left->next;
// Advance right pointer
right = right->prev;
}
}
// Driver code
int main()
{
Node* head = newNode(5);
insert(&head, 4);
insert(&head, 3);
insert(&head, 2);
insert(&head, 1);
printList(head);
cout << "List After Reversing" << endl;
reverseList(&head);
printList(head);
return 0;
}
C
// C Program to Reverse a List using Data Swapping
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Insert a new node at the head of the list
void insert(struct Node** head, int val)
{
struct Node* temp;
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = val;
temp->next = *head;
temp->prev = NULL;
if ((*head) != NULL) {
(*head)->prev = temp;
}
(*head) = temp;
}
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp->next != NULL) {
printf("%d <--> ", temp->data);
temp = temp->next;
}
printf("%d\n", temp->data);
}
// Function to reverse the list
void reverseList(struct Node* head)
{
struct Node* left = head;
struct Node* right = head;
// Traverse the list and set right pointer to
// end of list
while (right->next != NULL) {
right = right->next;
}
// Swap data of left and right pointer and move
// them towards each other until they meet or
// cross each other
while (left != right && left->prev != right) {
// Swap data of left and right pointer
int temp = left->data;
left->data = right->data;
right->data = temp;
// Advance left pointer
left = left->next;
// Advance right pointer
right = right->prev;
}
}
int main()
{
// code
struct Node* head = NULL;
insert(&head, 5);
insert(&head, 4);
insert(&head, 3);
insert(&head, 2);
insert(&head, 1);
printList(head);
printf("List After Reversing\n");
reverseList(head);
printList(head);
return 0;
// This code is contributed by lokesh (lokeshmvs21)
}
Java
// Java Program to Reverse a List using Data Swapping
class GFG
{
static class Node
{
int data;
Node prev, next;
};
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.prev = temp.next = null;
return temp;
}
static void printList(Node head)
{
while (head.next != null)
{
System.out.print(head.data+ " <-> ");
head = head.next;
}
System.out.println( head.data );
}
// Insert a new node at the head of the list
static Node insert(Node head, int val)
{
Node temp = newNode(val);
temp.next = head;
(head).prev = temp;
(head) = temp;
return head;
}
// Function to reverse the list
static Node reverseList(Node head)
{
Node left = head, right = head;
// Traverse the list and set right pointer to
// end of list
while (right.next != null)
right = right.next;
// Swap data of left and right pointer and move
// them towards each other until they meet or
// cross each other
while (left != right && left.prev != right)
{
// Swap data of left and right pointer
int t = left.data;
left.data = right.data;
right.data = t;
// Advance left pointer
left = left.next;
// Advance right pointer
right = right.prev;
}
return head;
}
// Driver code
public static void main(String args[])
{
Node head = newNode(5);
head = insert(head, 4);
head = insert(head, 3);
head = insert(head, 2);
head = insert(head, 1);
printList(head);
System.out.println("List After Reversing");
head=reverseList(head);
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 Program to Reverse a List
# using Data Swapping
import math
class Node:
def __init__(self, data):
self.data = data
self.next = None
def newNode(val):
temp = Node(val)
temp.data = val
temp.prev =None
temp.next = None
return temp
def printList( head):
while (head.next != None):
print(head.data, end = "<-->")
head = head.next
print(head.data)
# Insert a new node at the head of the list
def insert(head, val):
temp = newNode(val)
temp.next = head
(head).prev = temp
(head) = temp
return head
# Function to reverse the list
def reverseList( head):
left = head
right = head
# Traverse the list and set right
# pointer to end of list
while (right.next != None):
right = right.next
# Swap data of left and right pointer
# and move them towards each other
# until they meet or cross each other
while (left != right and left.prev != right):
# Swap data of left and right pointer
t = left.data
left.data = right.data
right.data = t
# Advance left pointer
left = left.next
# Advance right pointer
right = right.prev
return head
# Driver code
if __name__=='__main__':
head = newNode(5)
head = insert(head, 4)
head = insert(head, 3)
head = insert(head, 2)
head = insert(head, 1)
printList(head)
print("List After Reversing")
head = reverseList(head)
printList(head)
# This code is contributed by AbhiThakur
C#
// C# Program to Reverse a List using Data Swapping
using System;
class GFG
{
public class Node
{
public int data;
public Node prev, next;
};
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.prev = temp.next = null;
return temp;
}
static void printList(Node head)
{
while (head.next != null)
{
Console.Write(head.data+ " <-> ");
head = head.next;
}
Console.WriteLine( head.data );
}
// Insert a new node at the head of the list
static Node insert(Node head, int val)
{
Node temp = newNode(val);
temp.next = head;
(head).prev = temp;
(head) = temp;
return head;
}
// Function to reverse the list
static Node reverseList(Node head)
{
Node left = head, right = head;
// Traverse the list and set right pointer to
// end of list
while (right.next != null)
right = right.next;
// Swap data of left and right pointer and move
// them towards each other until they meet or
// cross each other
while (left != right && left.prev != right)
{
// Swap data of left and right pointer
int t = left.data;
left.data = right.data;
right.data = t;
// Advance left pointer
left = left.next;
// Advance right pointer
right = right.prev;
}
return head;
}
// Driver code
public static void Main(String []args)
{
Node head = newNode(5);
head = insert(head, 4);
head = insert(head, 3);
head = insert(head, 2);
head = insert(head, 1);
printList(head);
Console.WriteLine("List After Reversing");
head=reverseList(head);
printList(head);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// javascript Program to Reverse a List using Data Swapping
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
function newNode(val) {
var temp = new Node();
temp.data = val;
temp.prev = temp.next = null;
return temp;
}
function printList(head) {
while (head.next != null) {
document.write(head.data + " <-> ");
head = head.next;
}
document.write(head.data);
}
// Insert a new node at the head of the list
function insert(head , val) {
var temp = newNode(val);
temp.next = head;
(head).prev = temp;
(head) = temp;
return head;
}
// Function to reverse the list
function reverseList(head) {
var left = head, right = head;
// Traverse the list and set right pointer to
// end of list
while (right.next != null)
right = right.next;
// Swap data of left and right pointer and move
// them towards each other until they meet or
// cross each other
while (left != right && left.prev != right) {
// Swap data of left and right pointer
var t = left.data;
left.data = right.data;
right.data = t;
// Advance left pointer
left = left.next;
// Advance right pointer
right = right.prev;
}
return head;
}
// Driver code
var head = newNode(5);
head = insert(head, 4);
head = insert(head, 3);
head = insert(head, 2);
head = insert(head, 1);
printList(head);
document.write("<br/>List After Reversing<br/>");
head = reverseList(head);
printList(head);
// This code contributed by umadevi9616
</script>
1 <--> 2 <--> 3 <--> 4 <--> 5 List After Reversing 5 <--> 4 <--> 3 <--> 2 <--> 1
Complejidad de tiempo: O(n) , ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA