如果我创建了一个插入顺序为 5,4,3 的链表。我使用头引用，因此链接列表存储为 3->4->5->null。
当我想反转链表==原始插入顺序时，它会是
5->4->3->null。现在，如果这就是我的新列表的样子，我的头引用应该引用哪个节点，以便我添加到列表中的新元素仍然具有 O(1) 插入时间？
最佳答案
我认为 head，根据定义，总是指向列表的第一个元素。
如果要在 O(1) 内插入到链表的末尾，则保留两个引用，一个指向第一个元素，一个指向最后一个元素。然后添加到末尾是通过跟踪最后一个元素的最后一个引用来完成的，将新元素添加到最后一个元素之外，更新最后一个引用以指向新的最后一个元素。
插入到空列表成为一种特殊情况，因为您必须设置第一个和最后一个引用，而不仅仅是最后一个引用。类似地，从列表中删除一个元素。
关于java - 关于反转单链表的递归实现问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6076468/