快慢指针-小记

发布时间 2023-04-03 13:35:26作者: 黑熊一只

快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。最后,慢指针就是中位数。

这个理论,是建立在中位数 = n / 2的基础上。

同时,适用于: 单向链表查找。

这个理论,需要一个简易的规律总结即可自证。

[1, 2, 3]

lowPoint: 右移一步

fastPoint: 右移二步

终结条件判断: lowPoint.Next != nil && fastPoint.Next != nil

那么fastPoint指向到3时,循环终结,此时,慢指针为: 2.

[1, 2, 3, 4]

[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

lowPoint: 右移 8 步

fastPoint: 右移 8 * 2 步,此刻fastPoint将指向nil,循环终结。

而lowPoint,为: 8.