以递归方式反转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中的方法）从下往上开始更容易：

1. null的反转是什么（空列表）？空值。

2. 单元素列表的反转是什么？元素。

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