Invertendo uma linked list em Java, recursivamente

Eu tenho trabalhado em um projeto Java para uma aula por um tempo agora. É uma implementação de uma lista encadeada (aqui chamada AddressList , contendo nós simples chamados ListNode ). O problema é que tudo teria que ser feito com algoritmos recursivos. Eu era capaz de fazer tudo bem sans um método: public AddressList reverse()

ListNode:

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

No momento, minha function reverse apenas chama uma function auxiliar que usa um argumento para permitir a recursion.

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

Com a minha function auxiliar com a assinatura de private ListNode reverse(ListNode current) .

No momento, tenho que trabalhar iterativamente usando uma pilha, mas isso não é o que a especificação exige. Eu encontrei um algoritmo em C que recursivamente reverteu e converteu para código Java manualmente, e funcionou, mas eu não tinha conhecimento disso.

Edit: Nevermind, eu descobri nesse meio tempo.

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

Enquanto estou aqui, alguém vê algum problema com essa rota?

Há um código em uma resposta que soletra, mas você pode achar mais fácil começar de baixo para cima, perguntando e respondendo a pequenas perguntas (essa é a abordagem em The Little Lisper):

  1. Qual é o reverso de null (a lista vazia)? nulo.
  2. Qual é o reverso de uma lista de um elemento? o elemento.
  3. Qual é o reverso de uma lista de elementos n? o reverso do segundo elemento seguido pelo primeiro 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; } 

Fiz essa pergunta em uma entrevista e fiquei aborrecido por ter me atrapalhado com ela desde que estava um pouco nervoso.

Isso deve inverter uma lista ligada, chamada com reverso (head, NULL); Então, se esta fosse sua lista:

  1-> 2-> 3-> 4-> 5-> null
 isso se tornaria:
 5-> 4-> 3-> 2-> 1-> null 
 //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 } 

Editar: ive feito como 6 edições sobre isso, mostrando que ainda é um pouco complicado para mim lol

Cheguei na metade (até null, e um nó como sugerido por plinth), mas perdi a pista depois de fazer uma chamada recursiva. No entanto, depois de ler o post por plinth, aqui está o que eu fiz:

 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; } 

Aqui está outra solução recursiva. Ele tem menos código dentro da function recursiva do que alguns dos outros, então pode ser um pouco mais rápido. Este é o C #, mas acredito que o Java seria muito semelhante.

 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); } } 

O algoritmo precisará trabalhar no seguinte modelo,

  • acompanhar a cabeça
  • Recurse até o final da lista de links
  • Ligação reversa

Estrutura:

 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; } 

Saída:

 head-->12345 head-->54321 

Eu acho que isso é solução mais limpa, que se assemelha 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; } 

Eu sei que este é um post antigo, mas a maioria das respostas não é tail recursiva, ou seja, eles fazem algumas operações depois de retornar da chamada recursiva e, portanto, não o mais eficiente.

Aqui está uma versão recursiva da cauda:

 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. } 

Ligue com:

 Node newHead = reverse(head, head.getNext()); 
 void reverse (node1, node2) {
 if (node1.next! = null)
       reverso (node1.next, node1);
    node1.next = node2;
 }
 chame esse método como reverso (start, null);
 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; } 

Reverse 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; } 

Essa solução demonstra que nenhum argumento é necessário.

 /** * 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 } 

Aqui está o código de suporte, para demonstrar que isso 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()); } } 

Aqui está uma abordagem iterativa simples:

 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; } 

E aqui está uma abordagem recursiva:

 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 é sempre pass-by-value, para reverter recursivamente uma lista encadeada em Java, certifique-se de retornar o “novo header” (o nó principal após a reversão) no final da recursion.

 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); } } 

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

O que outros caras fizeram, no outro post é um jogo de conteúdo, o que eu fiz é um jogo de linkedlist, ele inverte o membro do LinkedList não reverso de um valor de membros.

 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+" "); } } } 

A solução é:

 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 tem resposta elegante e o mesmo em 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); } 

É assim que faríamos isso em Opal – uma linguagem de functional programming pura. E, IMHO – fazendo isso recursivamente só faz sentido nesse contexto.

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

rest (l) retorna uma lista que é a lista original sem seu primeiro nó. first (l) retorna o primeiro elemento. :: é um operador de concatenação.

 //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 um artigo discutindo implementações imutáveis ​​de estruturas de dados recursivas, eu juntei uma solução alternativa usando o Swift.

A resposta principal documenta a solução destacando os seguintes tópicos:

  1. Qual é o reverso de nil (a lista vazia)?
    • Não importa aqui, porque temos proteção nula no Swift.
  2. Qual é o reverso de uma lista de um elemento?
    • O elemento em si
  3. Qual é o reverso de uma lista de elementos n?
    • O reverso do segundo elemento é seguido pelo primeiro elemento.

Eu os chamei onde aplicável na solução abaixo.

 /** 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) } 

Invertendo a linked list usando recursion. A ideia é ajustar os links invertendo os links.

  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; }