反转单向链表 [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
}