力扣刷题笔记：反转链表与LRU缓存

"力扣500题刷题笔记4，涉及两道LeetCode上的经典链表问题：206.反转链表和146.LRU缓存机制" 在这篇刷题笔记中，作者首先讨论了LeetCode上的第206题——反转链表。反转链表是一个常见的链表操作，其目标是将链表中的节点顺序反转。题目给出的示例显示，链表可能包含任意数量的节点，范围在0到5000之间，且每个节点的值在-5000到5000之间。解决这个问题有两种方法：迭代和递归。 对于迭代解法，我们通常需要两个辅助指针，一个用于跟踪当前节点（`cur`），另一个用于跟踪前驱节点（`prev`）。初始时，`prev`设为`NULL`，`cur`设为链表头节点。在遍历过程中，我们先保存当前节点的后继节点，然后将当前节点的`next`指针指向`prev`，最后更新`prev`和`cur`指针，以便下一次迭代。这个过程持续到`cur`为空，此时`prev`就是反转后的链表头节点。整个过程的空间复杂度为O(1)，因为我们只使用了常量级别的额外空间，而时间复杂度是O(n)，其中n是链表的长度。 接下来，笔记提到了LeetCode上的第146题——LRU缓存机制。LRU（Least Recently Used）是一种常用的缓存淘汰策略，当缓存满时，会优先淘汰最近最少使用的数据。设计一个LRUCache类，需要实现两个方法：`get`和`put`。`get`方法返回键值对在缓存中的值，如果不存在则返回-1；`put`方法插入或更新键值对，当容量满时，需要移除最不经常使用的键值对。 实现LRUCache的关键是使用数据结构来支持O(1)的时间复杂度操作。一种常见的解决方案是结合哈希表和双向链表。哈希表用于快速查找键，双向链表用于保持最近使用的顺序。当`put`或`get`操作发生时，相应的节点会在链表中移动，以反映最新的访问顺序。如果`get`操作返回的键不存在，或者`put`操作导致容量超出限制，就需要从链表尾部移除最不常使用的节点，并从哈希表中删除对应的键。这样，`get`和`put`操作都能在O(1)时间内完成。 这两道题考察了链表操作和高级数据结构的设计与实现，是提升算法和数据结构能力的好题目。通过练习这样的题目，开发者可以更好地理解和运用链表、哈希表等数据结构，以及掌握如何在特定约束下优化时间复杂度。