快慢指针

以下内容仅为刷题总结，只记录目前遇到过的情况，如果后面遇到了更多可能性再做记录。

快慢指针

快慢指针的主要思想有点类似追击问题，通过让两个不同的小人以不同的速度在线性路径上行进，来招到某个特殊的相对位置。通常可以用来解决大致一下两类问题：

1. 线性路径上某特殊点的位置和对应的操作
2. 判断链表中是否存在循环（以及循环的点位置）

思路

一般的思路是让两个不同的小人先以某一个相对的路径进行移动，之后再以一定倍率的相对速度进行继续移动，如果发生了『追击』、『相遇』或者『触底』等特殊事件的时候，就可以作为解题需要的特殊位置来进行处理。

举例一：回文链表

如何判断出链表的中点位置？

答：通过两个速度分别为v和2v的指针同时从表头开始出发，当2v速度的指针『触底』的时候，以速度v前进的指针指向的位置理应为中点。

如果链表的长度为偶数的话，具体是停留在中间位置的左边还是右边要结合具体情况进行判断

举例二：环形链表

如何判断链表内是否有循环？

答：让两个不同速度的指针分别出发，如果有环存在的话，则必然会有两个指针在环内相遇。

举例三：环形链表 II

如何判断链表内开始进入环的位置？

答：让两个指针分别以速度v和2v出发，相遇则说明环存在。这个时候假入环前的长度为D，设环的长度为C，入环点到相遇点的距离为S1，相遇点重新回到入环点的距离则为S2。

• 此时快指针比慢指针多走n圈，所以走的距离必然为D+S1+nC
• 慢指针走一圈的时候，快指针能走两圈。所以相遇必然发声在第一个环内，所以慢指针走的距离为D+S1
• 由于2 * (D + S1) == D + S1 + nC和C = S1 + S2，所以不难得出D = (n - 1)(S1 + S2) + S2，即D = (n - 1)C + S2的结论，翻译一下则为，入环点前面的长度D即为慢指针再走S2，到达入环点之后，再走n-1圈的长度。
• 所以这个时候只需要再设定一个指针，让它从头开始走，当走到入环点D的时候，理论上来说慢指针也将走完第n-1圈，所以他们会相遇，同时慢指针的步数即为进入环的长度！

举例四：倒数第N个节点

如何删除链表中的倒数第N个节点？

答：让两个起始位置相差n的指针以同样的速度运动，当前面的指针『触底』的时候，后面的指针自己就是「倒数第n个」节点了。

实际操作的时候，由于单向链表需要知道前一个节点才能对后一个节点进行操作，所以通常会让走的快的节点比自己先走一步。