快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动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.
标签:右移,快慢,lowPoint,nil,fastPoint,小记,指针 From: https://www.cnblogs.com/supermarx/p/17282807.html