递归地反转Java中的链表

Question

我一直在为一个类的 Java 项目工作一段时间。它是链表的实现（这里称为 AddressList ，包含称为 ListNode 的简单节点）。问题是一切都必须用递归算法来完成。我能够在没有一种方法的情况下做任何事情： public AddressList reverse()

列表节点：

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

当我在这里时，有人看到这条路线有什么问题吗？

原文由 sdellysse 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

原文由 plinth 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我在一次采访中被问到这个问题，我很生气，因为我有点紧张，所以我笨手笨脚地回答了这个问题。

这应该反转一个单向链表，调用 reverse(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 次编辑，表明它对我来说仍然有点棘手哈哈

原文由 Ari Ronen 发布，翻译遵循 CC BY-SA 3.0 许可协议