SilentSpiral

链表,快慢指针与数论

Question:

  1. 判断链表是否成环
  2. 寻找链表成环位置
  3. 判断链表是否交尾共尾
  4. 链表实现二分查找

Q1: 判断链表是否成环

想必这个问题相当多的人都知道答案: 快慢指针判断相遇

但何谓快慢指针? 快者多快? 慢者多慢?
快指针速度Vf, 慢指针速度Vs, 环长k, 设慢指针刚刚进入环路时, 距离快指针m

据此列出相遇状态同余方程, 设经过时间为t:
　　(Vf-Vs)*t≡m (mod k)
令a=(Vf-Vs)
当且仅当a,k互质时有:
　　t≡m*a-1 (mod k)
若a,k不互质,当m≡0 (mod a)时, 记m=r*a, 有:
　　a*t≡r*a (modk)
　　t≡r (mod k)

注:若t有解即说明快慢指针可相遇

所以我们得到快慢指针相遇的充要条件: (a,k)互质或m是a的倍数

在实际工程中, k和m都是不可控的: m是a的倍数这一条件完全不可能事先办到, 所以只能寄希望于前者, 即a,k互质, 易知k也是完全不可控的, 事实上k存不存在都是未知, 所以令a=1是唯一的选择, 即Vf-Vs=1

出于以上思路的构造:
Vf=4, Vs=1, k=9, 慢指针初次进入环路时坐标为0, 同时快指针坐标为5

1
2
3
4
5
6
7
Vf=4;Vs=1;a=0;b=5
for i in range(100):
    a=(a+Vf)%9
    b=(b+Vs)%9
    print(a,b)
    if(a==b):
    break

此时有a,b的坐标对陷入如下不相遇的循环:
(8,6)->(3,7)->(7,8)->(2,0)->(6,1)->(1,2)->(5,3)->(0,4)->(4,5)->(8,6)->(3,7)->…

那么只能令Vf=2, Vs=1了…
　　　　　　　　　　　　　　　　……..吗?

是个头, 矮十厘米.jpg
　　Vf=2, Vs=1
　　Vf=3, Vs=2
　　Vf=4, Vs=3
　　Vf=5, Vs=4
　　……

但之所以通常要令Vf=2, Vs=1, 是因为……

Q2:寻找链表成环位置

算法:

Vf=2, Vs=1 (注: 只有这一对速度可以)
在快慢指针相遇时, 用另一个慢指针从链表起点出发, 两个慢指针相遇时便指向成环的节点

证明

慢指针速度Vs=1,快指针速度Vf=Vs+1=2;
环长k,成环前长度为l;

若Vs≠1, 则只有l是Vs的倍数或Vs与k互质时才能保证慢指针一定过成环处节点
鉴于l与k皆未知, 所以只能选择Vs=1才能使慢指针一定经过成环处节点

慢指针刚刚进入环路时, 一定处于成环处节点, 设此处为坐标原点, 此时快指针坐标为l
快慢指针相遇时有同余方程:
(Vf-Vs)*t≡-l (mod k) (注意此时从追击问题的角度其实是慢指针领先快指针k-r)
t≡-l (mod k)
所以快慢指针相遇时慢指针位于坐标为(k-l)的节点
此时再向起点出放置一个慢指针,则经过l个周期, 两指针皆指向成环处节点

Q3:判断链表是否交尾共尾

其实分别遍历到最后一个节点就可以了, 但还有一个有趣的思路:
将链表1的尾节点指向链表2的首节点, 再从链表2开始用快慢指针遍历判断是否成环

Q4:链表实现二分查找

跳跃表了解一下

它允许快速查询一个有序连续元素的数据链表，它的效率可以做到和二分相同，都是O(logn)的平均时间复杂度，其空间复杂度为O(n)
具体来说,其占用空间不会超过2n
\(n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+...=\cfrac{n(1-(1/2)^n)}{1-1/2}≤2n​\)

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。
跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。—-by 发明者
像是redis中有序集合就使用到了跳跃表。 (面试官的微笑)

打赏