快慢指针

 

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

快慢指针

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

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

思路

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

举例一:回文链表

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

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

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

举例二:环形链表

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

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

举例三:环形链表 II

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

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

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

举例四:倒数第N个节点

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

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

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