反转单向链表[Java]

Question

我想知道是否有人可以帮助解释如何在不创建新节点或更改现有节点中的数据的情况下反转单链表。我正在努力准备期末考试，我们在之前的一次考试中遇到了这个问题。他们不会发布测试代码部分的答案，我也没能弄清楚。

他们告诉我们逆转它的最好方法是使用“跑步者技术”，我相信我知道这是什么。他们将其描述为使用两个指针或计数器来遍历列表并收集信息，但我不确定如何使用它来反转单个点赞列表。我可以通过暴力破解代码来反转长度为2、3和4的列表，但我无法执行循环或递归操作。任何关于如何去做的代码或解释将不胜感激，谢谢。

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

你就完事了..。

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
}