Dada una lista enlazada, la tarea es escribir un programa en Java que invierta la lista enlazada sin manipular sus punteros, es decir, la inversión debe ocurrir simplemente cambiando los valores de los datos y no los enlaces.
Ejemplos:
Input: Original linked list 1->2->3->4->5->null Output: Linked list after reversal 5->4->3->2->1->null Input: Original linked list 5->14->20->8->null Output: Linked list after reversal 8->20->14->5->null Input: Original linked list 80->null Output: Linked list after reversal 80->null
Para la inversión, no se realiza ninguna manipulación en los enlaces que conectan el Node de la lista enlazada. Solo se modifican los valores de los datos. Para entender esto más claramente, eche un vistazo al siguiente diagrama.
Los números en color rojo representan las direcciones de los Nodes. Cabe señalar que incluso después de la inversión, los enlaces permanecieron iguales, es decir, antes de la inversión, el Node de la dirección 100 estaba conectado al Node de la dirección 200 , que a su vez estaba conectado al Node de la dirección 300 y así sucesivamente . , y estas conexiones también se han mantenido igual después de la reversión.
Acercarse:
- Las variables ‘l’ y ‘r’ se inicializan como 0 y tamaño-1 respectivamente, denotando el índice del primer y último Node.
- En un bucle, se obtienen los Nodes en el índice ‘l’ y ‘r’ y se intercambian los valores de datos correspondientes. El ciclo funciona incrementando ‘l’ y decrementando ‘r’.
- Para obtener el Node en un índice particular, se define un método privado ‘fetchNode’.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to reverse a linked list without pointer
// manipulation
class Node {
int value;
Node next;
Node(int val)
{
value = val;
next = null;
}
}
public class LinkedList {
Node head;
// this function returns the Node which is at a
// particular index.
// (The index is passed as the argument)
private Node fetchNode(int index)
{
Node temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
// this function returns the size of linked list
int getSize(Node head)
{
Node temp = head;
int size = 0;
while (temp != null) {
size++;
temp = temp.next;
}
return size;
}
// function to reverse the linked list
void reverse()
{
int l = 0;
int r = getSize(this.head) - 1;
while (l < r) {
Node leftSideNode = fetchNode(l);
Node rightSideNode = fetchNode(r);
int t = leftSideNode.value;
leftSideNode.value = rightSideNode.value;
rightSideNode.value = t;
l++;
r--;
}
}
// function that prints the elements of linked list
void printLinkedList()
{
Node temp = this.head;
while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String[] args)
{
LinkedList list1 = new LinkedList();
list1.head = new Node(1);
list1.head.next = new Node(2);
list1.head.next.next = new Node(3);
list1.head.next.next.next = new Node(4);
list1.head.next.next.next.next = new Node(5);
System.out.println("Linked List Before Reversal: ");
list1.printLinkedList();
list1.reverse();
System.out.println("Linked List After Reversal: ");
list1.printLinkedList();
}
}
Complejidad de tiempo : O (n) donde n no es ningún Node en la lista enlazada
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por bhatiahansika99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA