Invertir una lista enlazada en Java, recursivamente

He estado trabajando en un proyecto de Java para una clase desde hace un tiempo. Es una implementación de una lista vinculada (aquí llamada AddressList , que contiene nodos simples llamados ListNode ). La trampa es que todo debería hacerse con algoritmos recursivos. Pude hacer todo bien sin un método: public AddressList reverse()

ListNode:

 public class ListNode{ public String data; public ListNode next; } 

En este momento, mi función reverse solo llama a una función auxiliar que toma un argumento para permitir la recursión.

 public AddressList reverse(){ return new AddressList(this.reverse(this.head)); } 

Con mi función auxiliar con la firma del private ListNode reverse(ListNode current) .

Por el momento, lo tengo trabajando iterativamente usando una stack, pero esto no es lo que requiere la especificación. Encontré un algoritmo en C que invertía recursivamente y lo convertía a código Java a mano, y funcionaba, pero no lo entendía.

Editar: No importa, me di cuenta mientras tanto.

 private AddressList reverse(ListNode current, AddressList reversedList){ if(current == null) return reversedList; reversedList.addToFront(current.getData()); return this.reverse(current.getNext(), reversedList); } 

Mientras estoy aquí, ¿alguien ve algún problema con esta ruta?

Hay un código en una respuesta que lo deletrea, pero puede que le resulte más fácil comenzar de abajo hacia arriba, haciendo y respondiendo preguntas pequeñas (este es el enfoque en The Little Lisper):

  1. ¿Cuál es el reverso de null (la lista vacía)? nulo.
  2. ¿Cuál es el reverso de una lista de un elemento? el elemento.
  3. ¿Cuál es el reverso de una lista de n elementos? el reverso del segundo elemento seguido por el primer elemento.

 public ListNode Reverse(ListNode list) { if (list == null) return null; // first question if (list.next == null) return list; // second question // third question - in Lisp this is easy, but we don't have cons // so we grab the second element (which will be the last after we reverse it) ListNode secondElem = list.next; // bug fix - need to unlink list from the rest or you will get a cycle list.next = null; // then we reverse everything from the second element on ListNode reverseRest = Reverse(secondElem); // then we join the two lists secondElem.Next = list; return reverseRest; } 

Me hicieron esta pregunta en una entrevista y me molestó que la buscara porque estaba un poco nerviosa.

Esto debería revertir una lista enlazada individualmente, llamada con reverse (head, NULL); entonces si esta fuera tu lista:

  1-> 2-> 3-> 4-> 5-> nulo
 se convertiría en:
 5-> 4-> 3-> 2-> 1-> nulo 
 //Takes as parameters a node in a linked list, and p, the previous node in that list //returns the head of the new list Node reverse(Node n,Node p){ if(n==null) return null; if(n.next==null){ //if this is the end of the list, then this is the new head n.next=p; return n; } Node r=reverse(n.next,n); //call reverse for the next node, //using yourself as the previous node n.next=p; //Set your next node to be the previous node return r; //Return the head of the new list } 

edit: He hecho 6 ediciones en este, mostrando que todavía es un poco complicado para mí lol

Llegué a la mitad (hasta nulo, y un nodo como lo sugiere el plinto), pero perdí la pista después de hacer una llamada recursiva. Sin embargo, después de leer la publicación por zócalo, esto es lo que se me ocurrió:

 Node reverse(Node head) { // if head is null or only one node, it's reverse of itself. if ( (head==null) || (head.next == null) ) return head; // reverse the sub-list leaving the head node. Node reverse = reverse(head.next); // head.next still points to the last element of reversed sub-list. // so move the head to end. head.next.next = head; // point last node to nil, (get rid of cycles) head.next = null; return reverse; } 

Aquí hay otra solución recursiva. Tiene menos código dentro de la función recursiva que algunos de los otros, por lo que podría ser un poco más rápido. Esto es C #, pero creo que Java sería muy similar.

 class Node { Node next; public T data; } class LinkedList { Node head = null; public void Reverse() { if (head != null) head = RecursiveReverse(null, head); } private Node RecursiveReverse(Node prev, Node curr) { Node next = curr.next; curr.next = prev; return (next == null) ? curr : RecursiveReverse(curr, next); } } 

El algo necesitará trabajar en el siguiente modelo,

  • realizar un seguimiento de la cabeza
  • Repetir hasta el final de la lista de enlaces
  • Enlace inverso

Estructura:

 Head | 1-->2-->3-->4-->N-->null null-->1-->2-->3-->4-->N<--null null-->1-->2-->3-->4<--N<--null null-->1-->2-->3<--4<--N<--null null-->1-->2<--3<--4<--N<--null null-->1<--2<--3<--4<--N<--null null<--1<--2<--3<--4<--N | Head 

Código:

 public ListNode reverse(ListNode toBeNextNode, ListNode currentNode) { ListNode currentHead = currentNode; // keep track of the head if ((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1 if (currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively currentNode.next = toBeNextNode; // reverse link return currentHead; } 

Salida:

 head-->12345 head-->54321 

Creo que esta es una solución más limpia, que se asemeja a LISP

 // Example: // reverse0(1->2->3, null) => // reverse0(2->3, 1) => // reverse0(3, 2->1) => reverse0(null, 3->2->1) // once the first argument is null, return the second arg // which is nothing but the reveresed list. Link reverse0(Link f, Link n) { if (f != null) { Link t = new Link(f.data1, f.data2); t.nextLink = n; f = f.nextLink; // assuming first had n elements before, // now it has (n-1) elements reverse0(f, t); } return n; } 

Sé que esta es una publicación anterior, pero la mayoría de las respuestas no son recursivas, es decir, realizan algunas operaciones después de regresar de la llamada recursiva y, por lo tanto, no son las más eficientes.

Aquí hay una versión recursiva de la cola:

 public Node reverse(Node previous, Node current) { if(previous == null) return null; if(previous.equals(head)) previous.setNext(null); if(current == null) { // end of list head = previous; return head; } else { Node temp = current.getNext(); current.setNext(previous); reverse(current, temp); } return null; //should never reach here. } 

Llamar con:

 Node newHead = reverse(head, head.getNext()); 
 void reverse (node1, node2) {
 if (node1.next! = null)
       reverse (node1.next, node1);
    node1.next = node2;
 }
 llama a este método como inverso (inicio, nulo);
 public Node reverseListRecursive(Node curr) { if(curr == null){//Base case return head; } else{ (reverseListRecursive(curr.next)).next = (curr); } return curr; } 
 public void reverse() { head = reverseNodes(null, head); } private Node reverseNodes(Node prevNode, Node currentNode) { if (currentNode == null) return prevNode; Node nextNode = currentNode.next; currentNode.next = prevNode; return reverseNodes(currentNode, nextNode); } 
 public static ListNode recRev(ListNode curr){ if(curr.next == null){ return curr; } ListNode head = recRev(curr.next); curr.next.next = curr; curr.next = null; // propogate the head value return head; } 

Reverso por algo recursivo

 public ListNode reverse(ListNode head) { if (head == null || head.next == null) return head; ListNode rHead = reverse(head.next); rHead.next = head; head = null; return rHead; } 

Por iterativo

 public ListNode reverse(ListNode head) { if (head == null || head.next == null) return head; ListNode prev = null; ListNode cur = head ListNode next = head.next; while (next != null) { cur.next = prev; prev = cur; cur = next; next = next.next; } return cur; } 

Esta solución demuestra que no se requieren argumentos.

 /** * Reverse the list * @return reference to the new list head */ public LinkNode reverse() { if (next == null) { return this; // Return the old tail of the list as the new head } LinkNode oldTail = next.reverse(); // Recurse to find the old tail next.next = this; // The old next node now points back to this node next = null; // Make sure old head has no next return oldTail; // Return the old tail all the way back to the top } 

Aquí está el código de soporte, para demostrar que esto funciona:

 public class LinkNode { private char name; private LinkNode next; /** * Return a linked list of nodes, whose names are characters from the given string * @param str node names */ public LinkNode(String str) { if ((str == null) || (str.length() == 0)) { throw new IllegalArgumentException("LinkNode constructor arg: " + str); } name = str.charAt(0); if (str.length() > 1) { next = new LinkNode(str.substring(1)); } } public String toString() { return name + ((next == null) ? "" : next.toString()); } public static void main(String[] args) { LinkNode head = new LinkNode("abc"); System.out.println(head); System.out.println(head.reverse()); } } 

Aquí hay un enfoque iterativo simple:

 public static Node reverse(Node root) { if (root == null || root.next == null) { return root; } Node curr, prev, next; curr = root; prev = next = null; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } 

Y aquí hay un enfoque recursivo:

 public static Node reverseR(Node node) { if (node == null || node.next == null) { return node; } Node next = node.next; node.next = null; Node remaining = reverseR(next); next.next = node; return remaining; } 

Como Java siempre es pasaje por valor, para invertir recursivamente una lista enlazada en Java, asegúrese de devolver el “nuevo encabezado” (el nodo principal después de la reversión) al final de la recursión.

 static ListNode reverseR(ListNode head) { if (head == null || head.next == null) { return head; } ListNode first = head; ListNode rest = head.next; // reverse the rest of the list recursively head = reverseR(rest); // fix the first node after recursion first.next.next = first; first.next = null; return head; } 
 public class Singlelinkedlist { public static void main(String[] args) { Elem list = new Elem(); Reverse(list); //list is populate some where or some how } //this is the part you should be concerned with the function/Method has only 3 lines public static void Reverse(Elem e){ if (e!=null) if(e.next !=null ) Reverse(e.next); //System.out.println(e.data); } } class Elem { public Elem next; // Link to next element in the list. public String data; // Reference to the data. } 
 public Node reverseRec(Node prev, Node curr) { if (curr == null) return null; if (curr.next == null) { curr.next = prev; return curr; } else { Node temp = curr.next; curr.next = prev; return reverseRec(curr, temp); } } 

llamada usando: head = reverseRec (null, head);

Lo que otros chicos hicieron, en otra publicación es un juego de contenido, lo que hice fue un juego de lista enlazada, invirtió el miembro de la Lista enlazada y no el valor invertido de los miembros.

 Public LinkedList reverse(LinkedList List) { if(List == null) return null; if(List.next() == null) return List; LinkedList temp = this.reverse( List.next() ); return temp.setNext( List ); } 
 package com.mypackage; class list{ node first; node last; list(){ first=null; last=null; } /*returns true if first is null*/ public boolean isEmpty(){ return first==null; } /*Method for insertion*/ public void insert(int value){ if(isEmpty()){ first=last=new node(value); last.next=null; } else{ node temp=new node(value); last.next=temp; last=temp; last.next=null; } } /*simple traversal from beginning*/ public void traverse(){ node t=first; while(!isEmpty() && t!=null){ t.printval(); t= t.next; } } /*static method for creating a reversed linked list*/ public static void reverse(node n,list l1){ if(n.next!=null) reverse(n.next,l1);/*will traverse to the very end*/ l1.insert(n.value);/*every stack frame will do insertion now*/ } /*private inner class node*/ private class node{ int value; node next; node(int value){ this.value=value; } void printval(){ System.out.print(value+" "); } } } 

La solucion es:

 package basic; import custom.ds.nodes.Node; public class RevLinkedList { private static Node first = null; public static void main(String[] args) { Node f = new Node(); Node s = new Node(); Node t = new Node(); Node fo = new Node(); f.setNext(s); s.setNext(t); t.setNext(fo); fo.setNext(null); f.setItem(1); s.setItem(2); t.setItem(3); fo.setItem(4); Node curr = f; display(curr); revLL(null, f); display(first); } public static void display(Node curr) { while (curr.getNext() != null) { System.out.println(curr.getItem()); System.out.println(curr.getNext()); curr = curr.getNext(); } } public static void revLL(Node pn, Node cn) { while (cn.getNext() != null) { revLL(cn, cn.getNext()); break; } if (cn.getNext() == null) { first = cn; } cn.setNext(pn); } 

}

 static void reverseList(){ if(head!=null||head.next!=null){ ListNode tail=head;//head points to tail ListNode Second=head.next; ListNode Third=Second.next; tail.next=null;//tail previous head is poiniting null Second.next=tail; ListNode current=Third; ListNode prev=Second; if(Third.next!=null){ while(current!=null){ ListNode next=current.next; current.next=prev; prev=current; current=next; } } head=prev;//new head } } class ListNode{ public int data; public ListNode next; public int getData() { return data; } public ListNode(int data) { super(); this.data = data; this.next=null; } public ListNode(int data, ListNode next) { super(); this.data = data; this.next = next; } public void setData(int data) { this.data = data; } public ListNode getNext() { return next; } public void setNext(ListNode next) { this.next = next; } } 
 private Node ReverseList(Node current, Node previous) { if (current == null) return null; Node originalNext = current.next; current.next = previous; if (originalNext == null) return current; return ReverseList(originalNext, current); } 
 //this function reverses the linked list public Node reverseList(Node p) { if(head == null){ return null; } //make the last node as head if(p.next == null){ head.next = null; head = p; return p; } //traverse to the last node, then reverse the pointers by assigning the 2nd last node to last node and so on.. return reverseList(p.next).next = p; } 

PointZeroTwo tiene una respuesta elegante y lo mismo en Java …

 public void reverseList(){ if(head!=null){ head = reverseListNodes(null , head); } } private Node reverseListNodes(Node parent , Node child ){ Node next = child.next; child.next = parent; return (next==null)?child:reverseListNodes(child, next); } 

Así es como lo haríamos en Opal, un lenguaje de progtwigción puramente funcional. Y, en mi humilde opinión, hacer esto recursivamente solo tiene sentido en ese contexto.

 List Reverse(List l) { if (IsEmpty(l) || Size(l) == 1) return l; return reverse(rest(l))::first(l); } 

rest (l) devuelve una lista que es la lista original sin su primer nodo. primero (l) devuelve el primer elemento. :: es un operador de concatenación.

 //Recursive solution class SLL { int data; SLL next; } SLL reverse(SLL head) { //base case - 0 or 1 elements if(head == null || head.next == null) return head; SLL temp = reverse(head.next); head.next.next = head; head.next = null; return temp; } 

Inspirado por un artículo sobre implementaciones inmutables de estructuras de datos recursivas, coloqué una solución alternativa usando Swift.

La solución de documentos de respuestas líder destacando los siguientes temas:

  1. ¿Cuál es el reverso de nil (la lista vacía)?
    • No importa aquí, porque no tenemos protección en Swift.
  2. ¿Cuál es el reverso de una lista de un elemento?
    • El elemento en sí
  3. ¿Cuál es el reverso de una lista de n elementos?
    • El reverso del segundo elemento seguido por el primer elemento.

Los he llamado cuando corresponda en la solución a continuación.

 /** Node is a class that stores an arbitrary value of generic type T and a pointer to another Node of the same time. This is a recursive data structure representative of a member of a unidirectional linked list. */ public class Node { public let value: T public let next: Node? public init(value: T, next: Node?) { self.value = value self.next = next } public func reversedList() -> Node { if let next = self.next { // 3. The reverse of the second element on followed by the first element. return next.reversedList() + value } else { // 2. Reverse of a one element list is itself return self } } } /** @return Returns a newly created Node consisting of the lhs list appended with rhs value. */ public func +(lhs: Node, rhs: T) -> Node { let tail: Node? if let next = lhs.next { // The new tail is created recursively, as long as there is a next node. tail = next + rhs } else { // If there is not a next node, create a new tail node to append tail = Node(value: rhs, next: nil) } // Return a newly created Node consisting of the lhs list appended with rhs value. return Node(value: lhs.value, next: tail) } 

Invertir la lista vinculada mediante recursión. La idea es ajustar los enlaces invirtiendo los enlaces.

  public ListNode reverseR(ListNode p) { //Base condition, Once you reach the last node,return p if (p == null || p.next == null) { return p; } //Go on making the recursive call till reach the last node,now head points to the last node ListNode head = reverseR(p.next); //Head points to the last node //Here, p points to the last but one node(previous node), q points to the last node. Then next next step is to adjust the links ListNode q = p.next; //Last node link points to the P (last but one node) q.next = p; //Set the last but node (previous node) next to null p.next = null; return head; //Head points to the last node } 
 public void reverseLinkedList(Node node){ if(node==null){ return; } reverseLinkedList(node.next); Node temp = node.next; node.next=node.prev; node.prev=temp; return; } 
 public void reverse(){ if(isEmpty()){ return; } Node revHead = new Node(); this.reverse(head.next, revHead); this.head = revHead; } private Node reverse(Node node, Node revHead){ if(node.next == null){ revHead.next = node; return node; } Node reverse = this.reverse(node.next, revHead); reverse.next = node; node.next = null; return node; }