Suponiendo que haya pasado por LinkedList en Java y conozca la lista vinculada. Esta publicación contiene diferentes ejemplos para revertir una lista vinculada que se detallan a continuación:
1. Escribiendo nuestra propia función (usando espacio adicional): el método reverseLinkedList() contiene lógica para invertir objetos de string en una lista enlazada. Este método toma una lista enlazada como parámetro, recorre todos los elementos en orden inverso y los agrega a la lista enlazada recién creada.
Algoritmo:
Paso 1. Cree una lista enlazada con n elementos
Paso 2. Cree una lista enlazada vacía que se usará para almacenar elementos invertidos
Paso 3. Comience a recorrer la lista de ‘n’ a ‘0’ y almacene los elementos en el nuevo lista creada.
Paso 4. Los elementos se almacenarán en el siguiente orden: n, n-1, n-2, ……0
Paso 5. Devuelva la lista a la persona que llama e imprímala
Example:
Step 1: LL: 1 -> 2 -> 3 -> 4 -> 5 where 'LL' is the linked list with n elements
Step 2: 'Rev' is an empty linked list
Step 3: Start traversing, the below passes are the intermediate steps while traversing
1st pass: Rev: 5
2nd pass: Rev: 5 -> 4
3rd pass: Rev: 5 -> 4 -> 3
4th pass: Rev: 5 -> 4 -> 3 -> 2
5th pass: Rev: 5 -> 4 -> 3 -> 2 -> 1
Step 4: nth element of 'LL' is stored in 0th position of 'Rev',
n-1 element of LL is stored in 1st position of Rev and so on......
Step 5: Return Rev: 5 -> 4 -> 3 -> 2 -> 1 to the calling function.
// Java program for reversing linked list using additional space
import java.util.*;
public class LinkedListTest1 {
public static void main(String[] args)
{
// Declaring linkedlist without any initial size
LinkedList<String> linkedli = new LinkedList<String>();
// Appending elements at the end of the list
linkedli.add("Cherry");
linkedli.add("Chennai");
linkedli.add("Bullet");
System.out.print("Elements before reversing: " + linkedli);
linkedli = reverseLinkedList(linkedli);
System.out.print("\nElements after reversing: " + linkedli);
}
// Takes a linkedlist as a parameter and returns a reversed linkedlist
public static LinkedList<String> reverseLinkedList(LinkedList<String> llist)
{
LinkedList<String> revLinkedList = new LinkedList<String>();
for (int i = llist.size() - 1; i >= 0; i--) {
// Append the elements in reverse order
revLinkedList.add(llist.get(i));
}
// Return the reversed arraylist
return revLinkedList;
}
}
Complejidad temporal: O(n)
Complejidad espacial: O(n)
NOTA: Como estamos utilizando espacio de memoria adicional para almacenar todos los elementos ‘n’ invertidos, la complejidad del espacio es O(n).
Elements before reversing: [Cherry, Chennai, Bullet] Elements after reversing: [Bullet, Chennai, Cherry]
2. Escribiendo nuestra propia función (sin usar espacio adicional): en el ejemplo anterior, se usa adicionalmente una lista enlazada para almacenar todos los elementos invertidos, lo que ocupa más espacio. Para evitar eso, se puede usar la misma lista enlazada para invertir.
Algoritmo:
1. Crear una lista enlazada con n elementos
1. Ejecutar el ciclo n/2 veces donde ‘n’ es el número de elementos en la lista enlazada.
2. En el primer pase, Intercambie el primer y el n-ésimo elemento
3. En el segundo pase, Intercambie el segundo y el (n-1)-ésimo elemento y así sucesivamente hasta llegar a la mitad de la lista enlazada.
4. Devuelva la lista enlazada después de la terminación del ciclo.
Example:
Input: 1 -> 2 -> 3 -> 4 -> 5
1st pass: (swap first and nth element)
5 -> 2 -> 3 -> 4 -> 1
2nd pass: (swap second and (n-1)th element)
5 -> 4 -> 3 -> 2 -> 1
3rd pass: (reached mid, Terminate loop)
5 -> 4 -> 3 -> 2 -> 1
Output: 5 -> 4 -> 3 -> 2 -> 1
// Java program for reversing an arraylist without
// using any additional space
import java.util.*;
public class LinkedListTest2 {
public static void main(String[] args)
{
// Declaring linkedlist without any initial size
LinkedList<Integer> linkedli = new LinkedList<Integer>();
// Appending elements at the end of the list
linkedli.add(new Integer(1));
linkedli.add(new Integer(2));
linkedli.add(new Integer(3));
linkedli.add(new Integer(4));
linkedli.add(new Integer(5));
System.out.print("Elements before reversing: " + linkedli);
// Calling user defined function for reversing
linkedli = reverseLinkedList(linkedli);
System.out.print("\nElements after reversing: " + linkedli);
}
// Takes a linkedlist as a parameter and returns a reversed linkedlist
public static LinkedList<Integer> reverseLinkedList(LinkedList<Integer> llist)
{
for (int i = 0; i < llist.size() / 2; i++) {
Integer temp = llist.get(i);
llist.set(i, llist.get(llist.size() - i - 1));
llist.set(llist.size() - i - 1, temp);
}
// Return the reversed arraylist
return llist;
}
}
Complejidad Temporal: O(n/2)
Complejidad Espacial: O(1)
Elements before reversing: [1, 2, 3, 4, 5] Elements after reversing: [5, 4, 3, 2, 1]
3. Mediante el uso de la clase Collections: Collections es una clase en el paquete java.util que contiene varios métodos estáticos para buscar, clasificar, invertir, encontrar máximos, mínimos, etc. Podemos hacer uso del método In-built Collections.reverse() para invertir una lista enlazada. Toma una lista como parámetro de entrada y devuelve la lista invertida.
NOTA: El método Collections.reverse() usa el mismo algoritmo que «Escribiendo nuestra propia función (sin usar espacio adicional)»
// Java program for reversing a linked list using
// In-built collections class
import java.util.*;
public class LinkedListTest3 {
public static void main(String[] args)
{
// Declaring linkedlist without any initial size
LinkedList<Integer> linkedli = new LinkedList<Integer>();
// Appending elements at the end of the list
linkedli.add(new Integer(1));
linkedli.add(new Integer(2));
linkedli.add(new Integer(3));
linkedli.add(new Integer(4));
linkedli.add(new Integer(5));
System.out.print("Elements before reversing: " + linkedli);
// Collections.reverse method takes a list as a
// parameter and returns the reversed list
Collections.reverse(linkedli);
System.out.print("\nElements after reversing: " + linkedli);
}
}
Complejidad Temporal: O(n/2)
Complejidad Espacial: O(1)
Elements before reversing: [1, 2, 3, 4, 5] Elements after reversing: [5, 4, 3, 2, 1]
4. Inversión de una lista vinculada de objetos definidos por el usuario: se crea una clase de empleado para crear objetos definidos por el usuario con ID de empleado, nombre de empleado, nombre de departamento como variables de clase que se inicializan en el constructor. Se crea una lista vinculada que solo toma objetos de empleado (definidos por el usuario). Estos objetos se agregan a la lista vinculada mediante el método add(). La lista enlazada se invierte usando el método incorporado reverse() de la clase Collections.
El método printElements() se usa para iterar a través de todos los objetos definidos por el usuario en la lista vinculada e imprimir la identificación del empleado, el nombre y el nombre del departamento para cada objeto.
// Java program for reversing a inkedlist of user defined objects
import java.util.*;
class Employee {
int empID;
String empName;
String deptName;
// Constructor for initializing the class variables
public Employee(int empID, String empName, String deptName)
{
this.empID = empID;
this.empName = empName;
this.deptName = deptName;
}
}
public class LinkedListTest4 {
public static void main(String[] args)
{
// Declaring linkedList without any initial size
LinkedList<Employee> linkedli = new LinkedList<Employee>();
// Creating user defined objects
Employee emp1 = new Employee(123, "Cherry", "Fashionist");
Employee emp2 = new Employee(124, "muppala", "Development");
Employee emp3 = new Employee(125, "Bullet", "Police");
// Appending all the objects to linkedList
linkedli.add(emp1);
linkedli.add(emp2);
linkedli.add(emp3);
System.out.print("Elements before reversing: ");
printElements(linkedli);
// Collections.reverse method takes a list as a parameter
// and returns the reversed list
Collections.reverse(linkedli);
System.out.print("\nElements after reversing: ");
printElements(linkedli);
}
// Iterate through all the elements and print
public static void printElements(LinkedList<Employee> llist)
{
for (int i = 0; i < llist.size(); i++) {
System.out.print("\n EmpID:" + llist.get(i).empID + ", EmpName:"
+ llist.get(i).empName + ", Department:" + llist.get(i).deptName);
}
}
}
Complejidad Temporal: O(n/2)
Complejidad Espacial: O(1)
Elements before reversing: EmpID:123, EmpName:Cherry, Department:Fashionist EmpID:124, EmpName:muppala, Department:Development EmpID:125, EmpName:Bullet, Department:Police Elements after reversing: EmpID:125, EmpName:Bullet, Department:Police EmpID:124, EmpName:muppala, Department:Development EmpID:123, EmpName:Cherry, Department:Fashionist
Consulte invertir una lista vinculada para invertir una lista vinculada definida por el usuario.