algorithm - 我在简化这个反转单链表的代码片段时哪里出错了？

Question

我在 CareerCup 上找到了一个反转单向链表的解决方案:

void reverse(node n, node prev) 
{
    if (n == null) { head = prev; return; }

    reverse(n.next, n);
    n.next = prev;
}

call reverse (head, null);

这很好理解和研究。如果原始列表是“1->2->3->4->5”，则反向输出将是“5->4->3->2-> 1.

我试图通过仅使用一个参数来稍微简化此解决方案，该参数是当前正在处理的节点:

void reverse2(Node n)
{
      if(n.next==null){ head = n;return; }

      reverse2(n.next);
      n=n.next.next;
}

call reverse2(head)

也许你已经看出来了，结果不对，方法执行完后，修改的仍然是“1->2->3->4->5”。

一开始我很迷茫，想了想，我觉得是我的错，就是这行:

n=n.next.next;

其中我计划将下一个节点指向当前节点，但是，在我当前的递归中，我正在处理节点“n”本身，我没有更改当前节点 n 的任何内容，因此结果列表根本没有改变。

我自己不是100%信服，请专家指点一下？谢谢。

Answer 1

你的算法的问题是它没有改变原始数据结构。原始算法是这样做的:

n.next = prev;

实际上反转了一个节点。你只需要调用:

n.next = prev;

它只是改变了方法的一个参数，但什么都不做。

我怀疑你是否可以用只接受一个参数的递归方法来解决这个问题，因为在修改当前节点 N(i) 之后你需要移动到下一个节点 N(i+1)，而那个下一个节点应该指向 N(i)。所以下一次调用应该知道 N(i) 和 N(i+1)。