以递归方式在Java中反转链表 [英] Reversing a linked list in Java, recursively

问题描述

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

I have been working on a Java project for a class for a while now. It is an implementation of a linked list (here called AddressList, containing simple nodes called ListNode). The catch is that everything would have to be done with recursive algorithms. I was able to do everything fine sans one method: public AddressList reverse()

ListNode：

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

现在我的 reverse 函数只是调用一个帮助函数，它接受一个参数来允许递归。

Right now my reverse function just calls a helper function that takes an argument to allow recursion.

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

我的帮助函数的签名为 private ListNode反向（ListNode current）。

With my helper function having the signature of private ListNode reverse(ListNode current).

目前，我使用堆栈迭代地工作，但这不是规范要求。我在C中发现了一个递归算法，并将其转换为Java代码，但是我没有理解它。

At the moment, I have it working iteratively using a stack, but this is not what the specification requires. I had found an algorithm in C that recursively reversed and converted it to Java code by hand, and it worked, but I had no understanding of it.

编辑：Nevermind，我在此期间想出了这一点。

Nevermind, I figured it out in the meantime.

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

当我在这里，有没有人看到这条路线有任何问题？ / p>

While I'm here, does anyone see any problems with this route?

推荐答案

在一个回复中有代码解释出来，但是您可能会发现从底层开始更容易，回答小问题（这是The Little Lisper中的方法）：

There's code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper):

1. null（空列表）的相反方向是什么？ 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;
}

这篇关于以递归方式在Java中反转链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！