反转单向链表 [Java]

Question

我想知道如何在不创建新节点或更改现有节点数据的情况下翻转一个单链表。我正在为期末考试而努力学习，我们在以前的测试中曾有过这个问题。他们没有公布测试的编码部分答案，我一直没有能够理解它。

他们告诉我们，最好的方法是使用“Runner技术”，我相信我知道这是什么了。他们将其描述为使用两个指针或计数器来遍历列表并收集信息，但我不确定如何使用它来翻转一个单向链接列表。我已经能够 brute-force 编写将长度为2、3和4的列表翻转的代码，但我无法制作循环或递归执行。任何关于如何进行此操作的代码或解释都将不胜感激，谢谢。

- Anthony Rulli

---

你应该查看这个问题：https://dev59.com/WWEh5IYBdhLWcg3wRRqh?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa - MiguelD

Answer 1

您可以通过以下思路推导代码：逐一从输入列表中弹出元素，并将它们推入一个最初为空的结果列表：

NODE reverse(NODE list) {
  NODE result = null;
  while (list != null) {
    NODE head = <pop the first node off list>
    <push head onto result>
  }
  return result;
}

结果将是输入的反转。现在用Java替换缺失的部分。

NODE reverse(NODE list) {
  NODE result = null;
  while (list != null) {
    // pop
    NODE head = list;
    list = list.next;
    // push
    head.next = result;
    result = head;
  }
  return result;
}

完成了...

- Gene

---

非常感谢，这对我帮助很大。我刚意识到这会创建一个新节点，而我忘记了我们不能这样做。有没有办法改变这个，使我不需要创建一个新节点？ - Anthony Rulli

@AnthonyRulli 没有创建新的 NODE；只是将现有节点的引用复制到变量中。如果你不能做到这一点，就没有办法使用列表进行最简单的操作了。 - Kevin Anderson

@AnthonyRulli 你为什么认为这会创建新的节点？这需要调用 new NODE()。正如你所看到的，没有这样的调用存在。 - Gene

Answer 2

这取决于您对列表的实现方式，但我会递归到末尾，然后反转引用。

void Reverse(List pList) {
   Reverse(pList, null, pList.First); // initial call
}

void Reverse(List pList, Node pPrevious, Node pCurrent) {
   if (pCurrent != null)
      Reverse(pList, pCurrent, pCurrent.Next);   // advance to the end

   else { // once we get to the end, make the last element the first element
      pList.First = pPrevious;
      return;
   }

   pCurrent.Next = pPrevious; // reverse the references on all nodes
} 

- Dave Cousineau