Invertir Singly Linked List Java

¿Puede alguien decirme por qué funciona mi código dosent? Quiero revertir una sola lista vinculada en Java: este es el método (que no funciona correctamente)

public void reverseList(){ Node before = null; Node tmp = head; Node next = tmp.next; while(tmp != null){ if(next == null) return; tmp.next = before; before = tmp; tmp = next; next = next.next; } } 

Y esta es la clase Node:

 public class Node{ public int data; public Node next; public Node(int data, Node next){ this.data = data; this.next = next; } } 

En la entrada 4-> 3-> 2-> 1 obtuve la salida 4. Lo depuré y establece los punteros correctamente, pero todavía no entiendo por qué solo da como resultado 4.

 Node next = tmp.next; while(tmp != null){ 

Entonces, ¿qué sucede cuando tmp == null?

Casi lo tienes, sin embargo.

 Node before = null; Node tmp = head; while (tmp != null) { Node next = tmp.next; tmp.next = before; before = tmp; tmp = next; } head = before; 

O en un nombre más bonito (?):

 Node reversedPart = null; Node current = head; while (current != null) { Node next = current.next; current.next = reversedPart; reversedPart = current; current = next; } head = reversedPart; 

Arte ASCII:

  <__<__<__ __ : reversedPart : head (__)__ __ __ head : current:> > > 
 public Node reverseList(Node node) { if (node == null || node.next == null) { return node; } Node currentNode = node; Node previousNode = null; Node nextNode = null; while (currentNode != null) { nextNode = currentNode.next; currentNode.next = previousNode; previousNode = currentNode; currentNode = nextNode; } return previousNode; } 

El método para revertir una lista vinculada es el siguiente;

Método inverso

 public void reverseList() { Node curr = head; Node pre = null; Node incoming = null; while(curr != null) { incoming = curr.next; // store incoming item curr.next = pre; // swap nodes pre = curr; // increment also pre curr = incoming; // increment current } head = pre; // pre is the latest item where // curr is null } 

Se necesitan tres referencias para invertir una lista: pre , curr , entrante

 ... pre curr incoming ... --> (n-1) --> (n) --> (n+1) --> ... 

Para revertir un nodo, debe almacenar el elemento anterior, de modo que pueda usar la estructura simple;

 curr.next = pre; 

Para revertir la dirección del elemento actual. Sin embargo, para iterar sobre la lista, debe almacenar el elemento entrante antes de la ejecución de la statement anterior porque al invertir la siguiente referencia del elemento actual, ya no se conoce el elemento entrante, por eso es necesaria una tercera referencia.

El código de la demo es el siguiente;

Clase de muestra LinkedList

 public class LinkedList { protected Node head; public LinkedList() { head = null; } public LinkedList(E[] list) { this(); addAll(list); } public void addAll(E[] list) { for(int i = 0; i < list.length; i++) add(list[i]); } public void add(E e) { if(head == null) head = new Node(e); else { Node temp = head; while(temp.next != null) temp = temp.next; temp.next = new Node(e); } } public void reverseList() { Node curr = head; Node pre = null; Node incoming = null; while(curr != null) { incoming = curr.next; // store incoming item curr.next = pre; // swap nodes pre = curr; // increment also pre curr = incoming; // increment current } head = pre; // pre is the latest item where // curr is null } public void printList() { Node temp = head; System.out.print("List: "); while(temp != null) { System.out.print(temp + " "); temp = temp.next; } System.out.println(); } public static class Node { protected E e; protected Node next; public Node(E e) { this.e = e; this.next = null; } @Override public String toString() { return e.toString(); } } } 

Código de prueba

 public class ReverseLinkedList { public static void main(String[] args) { Integer[] list = { 4, 3, 2, 1 }; LinkedList linkedList = new LinkedList(list); linkedList.printList(); linkedList.reverseList(); linkedList.printList(); } } 

Salida

 List: 4 3 2 1 List: 1 2 3 4 

Si esto no es tarea y estás haciendo esto “manualmente” a propósito, entonces recomendaría usar

 Collections.reverse(list); 

Collections.reverse () devuelve nulo, y su lista se invierte después de la llamada.

Podemos tener tres nodos previos, actuales y siguientes.

 public void reverseLinkedlist() { /* * Have three nodes ie previousNode,currentNode and nextNode When currentNode is starting node, then previousNode will be null Assign currentNode.next to previousNode to reverse the link. In each iteration move currentNode and previousNode by 1 node. */ Node previousNode = null; Node currentNode = head; while (currentNode != null) { Node nextNode = currentNode.next; currentNode.next = previousNode; previousNode = currentNode; currentNode = nextNode; } head = previousNode; } 
 public void reverse() { Node prev = null; Node current = head; Node next = current.next; while(current.next != null) { current.next = prev; prev = current; current = next; next = current.next; } current.next = prev; head = current; } 

Sé que la solución recursiva no es la óptima, pero solo quería agregar una aquí:

 public class LinkedListDemo { static class Node { int val; Node next; public Node(int val, Node next) { this.val = val; this.next = next; } @Override public String toString() { return "" + val; } } public static void main(String[] args) { Node n = new Node(1, new Node(2, new Node(3, new Node(20, null)))); display(n); n = reverse(n); display(n); } static Node reverse(Node n) { Node tail = n; while (tail.next != null) { tail = tail.next; } reverseHelper(n); return (tail); } static Node reverseHelper(Node n) { if (n.next != null) { Node reverse = reverseHelper(n.next); reverse.next = n; n.next = null; return (n); } return (n); } static void display(Node n) { for (; n != null; n = n.next) { System.out.println(n); } } } 

No lo entiendo … ¿por qué no hacer esto?

 private LinkedList reverseLinkedList(LinkedList originalList){ LinkedList reversedList = new LinkedList<>(); for(int i=0 ; i 

Encuentro esto más fácil.

Una solución más elegante sería usar recursión

 void ReverseList(ListNode current, ListNode previous) { if(current.Next != null) { ReverseList(current.Next, current); ListNode temp = current.Next; temp.Next = current; current.Next = previous; } } 
 Node reverse_rec(Node start) { if (start == null || start -> next == null) { return start; } Node new_start = reverse(start->next); start->next->next = start; start->next = null; return new_start; } Node reverse(Node start) { Node cur = start; Node bef = null; while (cur != null) { Node nex = cur.next; cur.next = bef; bef = cur; cur = nex; } return bef; 

}

Probé el siguiente código y funciona bien:

 Node head = firstNode; Node current = head; while(current != null && current.next != null){ Node temp = current.next; current.next = temp.next; temp.next = head; head = temp; } 

Básicamente, uno por uno establece el siguiente puntero de un nodo en el próximo nodo siguiente, de modo que a partir de ahora todos los nodos se adjuntan en la parte posterior de la lista.

Creo que su problema es que su atributo next next next next no se modifica debido a su condición

 if(next == null) return; 

Está al comienzo de tu ciclo.

Lo movería justo después de que se haya asignado tmp.next:

 while(tmp != null){ tmp.next = before; if(next == null) return; before = tmp; tmp = next; next = next.next; } 

Utilizar esta.

 if (current== null || current.next==null) return current; Node nextItem = current.next; current.next = null; Node reverseRest = reverse(nextItem); nextItem.next = current; return reverseRest 

o el progtwig Java para revertir una lista enlazada individualmente

 package com.three; public class Link { int a; Link Next; public Link(int i){ a=i; } } public class LinkList { Link First = null; public void insertFirst(int a){ Link objLink = new Link(a); objLink.Next=First; First = objLink; } public void displayLink(){ Link current = First; while(current!=null){ System.out.println(current.a); current = current.Next; } } public void ReverseLink(){ Link current = First; Link Previous = null; Link temp = null; while(current!=null){ if(current==First) temp = current.Next; else temp=current.Next; if(temp==null){ First = current; //return; } current.Next=Previous; Previous=current; //System.out.println(Previous); current = temp; } } public static void main(String args[]){ LinkList objLinkList = new LinkList(); objLinkList.insertFirst(1); objLinkList.insertFirst(2); objLinkList.insertFirst(3); objLinkList.insertFirst(4); objLinkList.insertFirst(5); objLinkList.insertFirst(6); objLinkList.insertFirst(7); objLinkList.insertFirst(8); objLinkList.displayLink(); System.out.println("-----------------------------"); objLinkList.ReverseLink(); objLinkList.displayLink(); } } 

también puedes probar esto

  LinkedListNode pointer = head; LinkedListNode prev = null, curr = null; /* Pointer variable loops through the LL */ while(pointer != null) { /* Proceed the pointer variable. Before that, store the current pointer. */ curr = pointer; // pointer = pointer.next; /* Reverse the link */ curr.next = prev; /* Current becomes previous for the next iteration */ prev = curr; } System.out.println(prev.printForward()); 

clase pública SinglyLinkedListImpl {

 private Node head; public void add(T element) { Node item = new Node(element); if (head == null) { head = item; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = item; } } private void reverse() { Node temp = null; Node next = null; while (head != null) { next = head.next; head.next = temp; temp = head; head = next; } head = temp; } void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(); } public static void main(String a[]) { SinglyLinkedListImpl sl = new SinglyLinkedListImpl(); sl.add(1); sl.add(2); sl.add(3); sl.add(4); sl.printList(sl.head); sl.reverse(); sl.printList(sl.head); } static class Node { private T data; private Node next; public Node(T data) { super(); this.data = data; } } 

}

 package LinkedList; import java.util.LinkedList; public class LinkedListNode { private int value; private LinkedListNode next = null; public LinkedListNode(int i) { this.value = i; } public LinkedListNode addNode(int i) { this.next = new LinkedListNode(i); return next; } public LinkedListNode getNext() { return next; } @Override public String toString() { String restElement = value+"->"; LinkedListNode newNext = getNext(); while(newNext != null) {restElement = restElement + newNext.value + "->"; newNext = newNext.getNext();} restElement = restElement +newNext; return restElement; } public static void main(String[] args) { LinkedListNode headnode = new LinkedListNode(1); headnode.addNode(2).addNode(3).addNode(4).addNode(5).addNode(6); System.out.println(headnode); headnode = reverse(null,headnode,headnode.getNext()); System.out.println(headnode); } private static LinkedListNode reverse(LinkedListNode prev, LinkedListNode current, LinkedListNode next) { current.setNext(prev); if(next == null) return current; return reverse(current,next,next.getNext()); } private void setNext(LinkedListNode prev) { this.next = prev; } } 
 public class ReverseLinkedList { public static void main(String args[]){ LinkedList linkedList = new LinkedList(); linkedList.add("a"); linkedList.add("b"); linkedList.add("c"); linkedList.add("d"); linkedList.add("e"); linkedList.add("f"); System.out.println("Original linkedList:"); for(int i = 0; i <=linkedList.size()-1; i++){ System.out.println(" - "+ linkedList.get(i)); } LinkedList reversedlinkedList = reverse(linkedList); System.out.println("Reversed linkedList:"); for(int i = 0; i <=reversedlinkedList.size()-1; i++){ System.out.println(" - "+ reversedlinkedList.get(i)); } } public static LinkedList reverse(LinkedList linkedList){ for(int i = 0; i < linkedList.size()/2; i++){ String temp = linkedList.get(i); linkedList.set(i, linkedList.get(linkedList.size()-1-i)); linkedList.set((linkedList.size()-1-i), temp); } return linkedList; } } 

Para revertir una lista enlazada por separado, debe tener tres nodos, arriba , antes de Top y AfterTop . La parte superior es el encabezado de la lista enlazada individualmente, por lo tanto beforeTop sería nulo y afterTop sería el siguiente elemento de la parte superior y con cada iteración avanzar antes de asignar Top y Top después de Top (es decir, top . Next ).

 private static Node inverse(Node top) { Node beforeTop=null, afterTop; while(top!=null){ afterTop=top.next; top.next=beforeTop; beforeTop=top; top=afterTop; } return beforeTop; } 

Usar la recursividad Es muy fácil:

 package com.config; import java.util.Scanner; public class Help { public static void main(String args[]){ Scanner sc = new Scanner(System.in); Node head = null; Node temp = null; int choice = 0; boolean flage = true; do{ Node node = new Node(); System.out.println("Enter Node"); node.data = sc.nextInt(); if(flage){ head = node; flage = false; } if(temp!=null) temp.next = node; temp = node; System.out.println("Enter 0 to exit."); choice = sc.nextInt(); }while(choice!=0); Help.getAll(head); Node reverse = Help.reverse(head,null); //reverse = Help.reverse(head, null); Help.getAll(reverse); } public static void getAll(Node head){ if(head==null) return ; System.out.println(head.data+"Memory Add "+head.hashCode()); getAll(head.next); } public static Node reverse(Node head,Node tail){ Node next = head.next; head.next = tail; return (next!=null? reverse(next,head) : head); } } class Node{ int data = 0; Node next = null; } 
  // Java program for reversing the linked list class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to reverse the linked list Node reverse(Node node) { Node prev = null; Node current = node; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } node = prev; return node; } // prints content of double linked list void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(85); list.head.next = new Node(15); list.head.next.next = new Node(4); list.head.next.next.next = new Node(20); System.out.println("Given Linked list"); list.printList(head); head = list.reverse(head); System.out.println(""); System.out.println("Reversed linked list "); list.printList(head); } } OUTPUT: - Given Linked list 85 15 4 20 Reversed linked list 20 4 15 85 
 Node Reverse(Node head) { Node n,rev; rev = new Node(); rev.data = head.data; rev.next = null; while(head.next != null){ n = new Node(); head = head.next; n.data = head.data; n.next = rev; rev = n; n=null; } return rev; } 

Use la función anterior para invertir la lista vinculada individual.

  public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } 

verifique más detalles sobre el análisis de complejidad http://javamicro.com/ref-card/DS-Algo/How-to-Reverse-Singly-Linked-List ?

 public static LinkedList reverseLinkedList(LinkedList node) { if (node == null || node.getNext() == null) { return node; } LinkedList remaining = reverseLinkedList(node.getNext()); node.getNext().setNext(node); node.setNext(null); return remaining; } 
 /** * Reverse LinkedList * @author asharda * */ class Node { int data; Node next; Node(int data) { this.data=data; } } public class ReverseLinkedList { static Node root; Node temp=null; public void insert(int data) { if(root==null) { root=new Node(data); } else { temp=root; while(temp.next!=null) { temp=temp.next; } Node newNode=new Node(data); temp.next=newNode; } }//end of insert public void display(Node head) { while(head!=null) { System.out.println(head.data); head=head.next; } } public Node reverseLinkedList(Node head) { Node newNode; Node tempr=null; while(head!=null) { newNode=new Node(head.data); newNode.next=tempr; tempr=newNode; head=head.next; } return tempr; } public static void main(String[] args) { ReverseLinkedList r=new ReverseLinkedList(); r.insert(10); r.insert(20); r.insert(30); r.display(root); Node t=r.reverseLinkedList(root); r.display(t); } } 
 public class Linkedtest { public static void reverse(List list) { int lenght = list.size(); for (int i = 0; i < lenght / 2; i++) { Object as = list.get(i); list.set(i, list.get(lenght - 1 - i)); list.set(lenght - 1 - i, as); } } public static void main(String[] args) { LinkedList st = new LinkedList(); st.add(1); st.add(2); st.add(3); st.add(4); st.add(5); Linkedtest.reverse(st); System.out.println("Reverse Value will be:"+st); } } 

Esto será útil para cualquier tipo de objeto de colección.