java - 反转链表

Question

我正在编写一个简单的递归代码来反转 Java 中的链表。奇怪的是它返回相同的节点。

Node reverse(Node ptr) {
    if (ptr.link == null)
        return ptr;

    Node second = ptr.link;
    ptr.link = null;

    Node rest = reverse(second);
    rest.link = ptr;

    return rest;
}

为什么这不起作用？

Answer 1

您当前的方法不起作用，从递归调用返回的 rest 值不会指向列表中的 last 元素(应该是节点的插入点)，而是指向结果的第一个元素。换句话说，这一行没有正确构建输出:

rest.link = ptr;

为了成功反转列表，一种策略是使用累加器参数，因此我们可以在递归展开时在列表的头部插入 - 请记住，递归开始以相反的顺序“返回”到列表中的元素。试试这个，它是 tail-recursive解决办法:

Node reverse(Node ptr, Node acc) {
    if (ptr == null)
        return acc;
    Node second = ptr.link;
    ptr.link = acc;
    return reverse(second, ptr);
}

像这样调用上面的方法:

Node reversedList = reverse(list, null);

请注意，输入列表将就地修改，并且在方法返回后不会相同，任何保存对的引用的变量>list 将受到影响。如果这是一个问题，您应该先创建一个 list 的副本，然后再将其传递给 reverse()。