以递归方式反转Java中的链表

Question

以递归方式反转Java中的链表

我一直在为一个类的Java项目工作。它是链表的实现（此处称为AddressList包含调用的简单节点ListNode）。问题在于，所有事情都必须通过递归算法来完成。我能做的一切都很好，没有一种方法：public AddressList reverse()

ListNode：

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

现在我的reverse函数只调用一个辅助函数，该函数接受一个允许递归的参数。

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

我的助手功能有签名private ListNode reverse(ListNode current)。

目前，我使用堆栈迭代地工作，但这不是规范要求的。我在C中找到了一个递归反转的算法，并手工将其转换为Java代码，但是它有效，但我对此并不了解。

编辑：没关系，我在此期间弄清楚了。

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

虽然我在这里，有没有人看到这条路线有任何问题？

Answer 1

一个回复中的代码说明了这一点，但是您可能会发现通过询问和回答微小的问题（这是The Little Lisper中的方法）从下往上开始更容易：null的反转是什么（空列表）？空值。单元素列表的反转是什么？元素。n元素列表的反转是什么？与列表其余部分相反的是第一个元素。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;}

Answer 2

我在接受采访时被问到这个问题，并且因为我有点紧张而感到烦恼。这应该反转一个单链表，用反向调用（head，NULL）; 所以如果这是你的清单：1-> 2-> 3-> 4-> 5->空它会变成：5-> 4-> 3-> 2-> 1->空     //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     }编辑：我已经完成了6次编辑，显示它对我来说仍然有点棘手lol

Answer 3

我得到了一半（直到null，并且由plinth建议的一个节点），但在进行递归调用后失去了轨道。然而，在阅读了基座的帖子后，我想出了以下内容：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;}