单链表的含环和相交性质探究过程记录

22 Sep, 2021

问题

如何判断单链表中是否存在环？如何判断两个单链表是否相交？如果相交，如何求出相交点？

思路

初见的思路

判断环：对链表进行遍历，如果无环则会访问到NULL，有环则会访问到head。
判断相交：单链表仅有一个next域，则相交必定是“两个均无环” 或 “一个有环一个无环"的两种情况。
初见的思路都有哪里不周全呢？经过接下来几天的考虑，我渐渐地意识到不周密之处所在…

修正后的思路

首先脱离形象上的“凭感觉”，尽管从形象上比较容易理解，但仍需要定义“含环”和“相交”的概念。

如果严格遵循单链表的ADT，是不会出现含环和相交的现象的。因为指针表示的是元素间的逻辑顺序，而ADT中并没有尾结点指向其他结点的逻辑关系。因此这里考虑的“单链表”应当仅指的是“结点的结构为：含有一个data域和一个next域”的数据结构。

含环：如果链表中的一个结点的next域仍指向这个表中的结点，则称链表含环。

相交：如果从L1出发，可以访问到L2中的结点，则称L1和L2相交。

最先意识到的错误：如果链表含环，在遍历它的过程中并不是一定会访问到head的，而且在通常情况下是不会访问到的，因为含环的链表实际上分为环外和环内两部分，而head只能处于环外的部分。另外，贸然对链表进行和原来一样形式的“遍历”是危险的。因为对于有环的链表来说，使用通常的遍历方法只会引起无穷递归。

另外，对相交的理解加深之后就可以意识到：原来理解的“一个有环一个无环”的情况，并不是真正的“一个有环一个无环”，事实上如果两个链表相交且一个有环，则另一个一定会访问到那个环，也就是说一定会推出“两个均含环”。如果一个链表有环，另一个链表无环，则它们一定不会相交。

进一步地，链表是否相交，可以分为七种情况。

实现和求解

预定义：

首先定义数据结构：

typedef struct {
Datatype data;
LNode* next;
}LNode;

我们需要实现的函数包括：

LNode* IfCircle(LNode* L); //判断是否有环
LNode* IfCross(LNode* L1, LNode* L2); //判断是否相交

判断是否有环的函数最开始是写成返回bool型的，返回1代表有环。但是在随后的IfCross的实现中，渐渐发现其实入环的点的位置相当重要。因此将IfCircle写成返回地址值的函数。

为什么说IfCross的实现依赖入环点？在它的七种情况中包括：

（两种）不含环的，可以通过一般的遍历方法求得交点或确认无交点；

（一种）一含环一不含环的，必然无交点；

两者都含环的：

”链表重合“和”链表完全不相关“：相对容易通过检测直接实现；
最麻烦的后两种”环内相交“和”环外相交“：如果环内相交，则两个交点就是两个链表的入环点；如果环外相交，那么也需要通过入环点限制遍历的条件，这样就可以使用一般的遍历方法进行遍历。

重要的工具：快慢指针

既然通常的遍历方式已经不适用，应当怎样对链表进行遍历呢？一个好办法是引入[[快慢指针]]。希望访问到所有的结点，可以要求快指针每次前进一步时就伴随访问一次结点）而从退出条件分析，将快者的速度设置为2，慢者的速度设置为1，则相当于快者相对于慢者每次严格前进1，环的长度有限，一定可以退出。更广泛地考虑下，慢者和快者的速度并不一定是1和2，在环长度L给定的情况下，只需要求（快指针速度-慢指针速度）和L互质即可。证明在后面给出。

通过快慢指针遍历最初是写在IfCircle函数中的，但在后来的实现中发现它在这里很常用，因此单独写一个函数出来。

int Traverse(LNode* start) {
/*
* return value:使用快慢两个指针遍历链表，若无环则返回0，有环则返回慢指针行进的距离。
*/
LNode* fast = start; LNode* slow = start;
if (start->next == NULL)
return 0;
int counter = 0;
while (slow = slow->next) {
counter++;
if (fast->next == NULL)return 0;
fast = fast->next;
if (fast->next == NULL)return 0;
fast = fast->next;
if (slow == fast)return counter;
}
}

快慢指针遍历带环链表的性质

关于快慢指针速度取值的证明

首先，只要要求快指针行进时，每一个小步(f = f->next)时都进行一次访问，就可以做到每个元素至少访问一遍，所以”遍历“的要求很容易满足。我们主要思考如何取值可以满足遍历的退出条件（f == s）。

显然，不管链表结构如何，在有限步内，快指针和慢指针都会进入环。所以我们只需要考虑均在环内时（初始位置不确定），快指针是否一定会赶上慢指针。这个问题等价于，慢指针不动，快指针以(快-慢)的速度移动，是否一定会走到慢指针。由于初始相对位置不确定，满足“一定会走到慢指针”的唯一途径就是“快指针在有限步内可以走到每一个环内结点”。从而问题可以抽象成如下形式：

设快指针的速度为$f$，慢指针的速度为$s$，环的长度为$L_c$，则快指针的相对速度为$v = f - s$。现有

$$iv\equiv b_i \pmod {L_c}.$$

其中$i$从$0$取到$L_c - 1$时，$b_i$也应取遍$\{0, 1, \dots , L_c - 1\}$.求满足此条件的$v$.

（解一）使用$Bezout$定理，只要$\gcd(v , L_c) = 1$，则$\exists c_1, c_2$, s.t.$c_1 v + c_2 L_c = 1.$，将$L_c v +(-v)L_c = 0$累加到上式中，一定可以得到$$c_1’ v = 1 + c_2’ L_c.(c_1 > 0)$$从而可以取遍$0$到$L_c-1$的值。

（解二）利用一个重要的性质：

$(a,m)=1, \forall b \in \mathbb{Z}, ax\equiv b\pmod m$，且$ax\equiv b\pmod m$有模$m$唯一的解。此时若考虑$b\in\{0,1,\dots,m-1\}, x\in \{0,1,\dots,m-1\}$，则此时$b$和$x$建立双射。

（证明）假设不构成一一映射，则必有$$x_1 a - b = k_1 m, x_2 a - b = k_2 m, x_1\not= x_2\in{0,1,\dots,m-1}. $$

那么有$$(x_1 - x_2) a = (k_1 - k_2) m.$$

由于$\gcd (a,m) = 1$，必定有$$m\mid (x_1 - x_2).$$

然而我们知道$ x_1\not= x_2\in{0,1,\dots,m-1} $，所以产生了矛盾。

故必定构成一一映射。

那么由上述性质我们有$$iv\equiv b_i\pmod{L_c}.$$

其中$i\in\{0,1,\dots,L_c-1\}, b\in\{0,1,\dots,L_c-1\}$，且$i$与$b_i$建立双射，故必然可以取到全部值。

在速度取分别取2和1时展现的性质

既然只需要速度的差与环长互质，而环长不确定，那么只能设置速度差为1。我们不妨取最方便实现的：快指针速度为2，慢指针速度为1.

我们希望IfCircle函数的返回值为入环点的地址，这经历了不小的困难。对一个一般的含环链表，我们假设环外部分的长度为$L_0$，环长度为$L_c$。在使用快慢指针遍历结束时，快慢指针分别走过的总路程为$L_f$和$L_s$，另假设慢指针进入环的那一时刻，它若向前追赶到快指针当时所处位置，所需的距离为$L_{fs}$。接下来对这些量之间的关系进行考察。

一个基础的性质：由于设定快指针f的步长为2，慢指针s的步长为1，易知：$$L_f = 2L_s.$$

由于s入环时与快指针的距离是$L_{fs}$，接下来相对s，f应行进的距离为$L_c - L_{fs}$，而相对s行进的距离等于s行进的绝对距离，故有：

$$L_s = L_0 + (L_c -L_{fs}).$$

而从出发到相遇，事实上快指针和慢指针相比，只是多在环内转几圈。故有：

$$L_f = L_0 + n L_c -L_{fs}.$$

另外由于s入环时行进了$L_0$，这时的f应当行进了$2L_0$，也就是在环内走了$L_0$的路程到达$L_{fs}$，则有：

$$L_0 \equiv L_{fs} \pmod {L_c}.$$

联立上述几个方程就可以得到：

$$L_s = (n-1) L_c.$$

这是一个非常好的性质，慢指针从出发到相遇，行进的绝对距离是环长度的整数倍。

接下来我们可以获取的量$L_f, L_s$可推导的就结束了，还有很多未知量，需要进一步探究。我们这时注意到f和s一定在环内相遇。我们从它们的相遇点开始再次使用快慢指针遍历，则此时$L_0’ = 0, L_{fs} = 0$，那么$$L_s’ = L_c.$$于是我们通过对环内结点的遍历得到了环的长度，进一步可以得到$n$的值。

但再继续对上面的方程操作，我们会发现$L_0 - L_{fs}$始终作为一个整体被消去、被求得。然而我们真正需要的是它们中的一个，这样才能求得入环点的地址。事实上如下图所示，现在我们需要的就是$L_0$和$L_{fs}$更精确的关系，也即在同余的基础上，它们到底差多少个$L_c$。

Traverse(head)的终点（相遇点）的性质

这里的信息隐含在：在s入环后，f相对s行进了 $L_c - L_{fs}$ ，则f行进的绝对距离应为$2(L_c - L_{fs})$. 我们有f在s入环前行进的距离为：

$$L_{f1} = 2L_0 = L_0 + (?) L_c +L_{fs}.$$

我们又知道了s入环后f行进的路程，和f行进的总路程：

$$L_{f2} = 2(L_c - L_{fs}).$$

$$L_f = L_0 + nLc - L_{fs} = L_{f1} + L_{f2}.$$

联立即得：

$$(?) = (n - 2).$$

那么同余式$L_0 \equiv L_{fs} \pmod {L_c}$便有了更精确的表达：

$$L_0 = (n-2)L_c + L_{fs}.$$

现在我们就可以找到入环点的地址了：只需令指针p从head先走$(n-2)L_c$，令指针q在Traverse(head)的相遇点，那么此时p和q与入环点的距离均为$L_{fs}$，且均朝向入环点。只需让他们以相同的步长前进，则相遇点即为环点。

LNode* IfCircle(LNode* head) {
/*
* return value: 若无环则返回NULL，有环则返回入环点的地址.
*/
if (!Traverse(head))return NULL;
//未退出，则有环。下一段算法和Traverse完全相同，只是此函数中return时返回的是地址。目的是得到环内的一个结点地址。
LNode* fast = head; LNode* slow = head;
while (slow = slow->next) {
fast = fast->next;
fast = fast->next;
if (slow == fast)break;//现在slow是环内的一个节点地址。
}

/*
* 关于单链表上环的性质的推导： 
* 假设从链表头到入环点处的长度为 L0, 环的长度为 Lc, 快指针行进路程为Lf, 慢指针行进路程为Ls,
* 慢指针进入环的时候，快慢指针之间的距离（以慢指针行进多远能赶上快指针计）为Lfs, 则Lfs与L0模Lc同余。
* 则Traverse(head)的过程中，Ls = L0 + Lc - Lfs; Lf = 2Ls = L0 + n * Lc - Lfs.
* 联立两方程则有Ls = (n-1) * Lc.
* 
* 下一步从相遇点开始Traverse(slow)，此时的Ls' = Lc; Lf' = 2Ls'. 也就是求出了Lc.
* 那么和上一步的Ls联立即可求出整数n，那么此时满足 (L0 + n * Lc - Lfs) = (L0 + ? * Lc + Lfs) + 2(Lc-Lfs)
* (等式右边前一项是s入环前，后一项是s入环后，其中的？表示在s入环前f转了多少圈)
* 所以在L0 ≡ Lfs (mod Lc)的基础上可以得到L0 = (n-2)Lc + Lfs.
* 于是可以找到到入环点的的地址:
* p = head; q = slow（指Traverse(head)的相遇点)，p前进(n-2)Lc步后，p和q距离入环点均为Lfs，故此时令它们均向前相遇即可。
*/

int Lc = Traverse(slow);//=Lc. 从环上一点开始遍历，必然是走（环的长度）距离时两指针相遇。
int Ls = Traverse(head);//=Ls = (n-1) * Lc.
int n = Ls / Lc + 1;
LNode* p = head; LNode* q = slow;
for (int i = 0; i < n - 2; i++)
p = p->next;
while (p != q) {
p = p->next;
q = q->next;
}
return p;
}

那么IfCross的实现在有了可以返回入环点的IfCircle帮助下可以较方便地实现：

LNode* IfCross(LNode* L1, LNode* L2) {
if ((IfCircle(L1) && !IfCircle(L2))  (!IfCircle(L1) && IfCircle(L2)))return NULL;
//一个有环，另一个无环，必定不相交。

LNode* p = L1; LNode* q = L2;
if (!(IfCircle(L1)  IfCircle(L2))) {//两个都无环
while (p->next)
p = p->next;
while (q->next)
q = q->next;
if (p != q)return NULL;//末地址不同，不相交
//执行到此步：相交
p = L1; q = L2;
do { //从L1的第一个节点开始，固定p，遍历q，若找不到相同则p = p->next，继续遍历q，如此循环。
while (q) {
if (p 
    q)return q;//p
 q：此时找到交点。
q = q->next;
}
q = L2;
} while (p = p->next);
}

else {//两个都有环
if (IfCircle(p) == IfCircle(q)) {//入环点是同一个，在环外相交。
LNode* CirPoint = IfCircle(p);
do { //从L1的第一个节点开始，固定p，遍历q至环点，若找不到相同则p = p->next，继续遍历q，如此循环。
while (q!= CirPoint) {
if (p 
    q)return q;//p
 q：此时找到交点。
q = q->next;
}
q = L2;
} while ((p = p->next) && p != CirPoint);
}//end if

else {//入环点不同，在环内相交。
return IfCircle(p);//在环内相交事实上有两个交点，由于C语言的限制此处只返回一个。
//事实上两个交点就是两个链表的入环点：IfCircle(p)和IfCircle(q).
}
}
}

#pointer