递归地反转Java中的链表

Question

我已经在一个类的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. 一个元素列表的反向作用是什么？元素。

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