链表 §

快慢指针 §

使用两个指针对链表进行遍历，且两个指针的移动速度不同。

用途：

• 寻找链表的中点（快指针一次移动两格，慢指针一次移动一格）；
• 判断链表是否成环（如果成环，快慢指针一定相遇）。

dummy 节点 §

在链表表头前加一个节点指向 head，这个节点被称为 dummy。使用 dummy 节点可以减少边界处理情况。

当链表的头节点发生变化后（如被删除），那么可以使用 return dummy.next 来返回修改后的链表。

双向链表 §

典型使用场景：LRU

相关题目 §

• 2 两数相加 (dummy 节点）
• 19 删除链表的倒数第N个节点（快慢指针）
• 21 合并两个有序链表