Problem

How do you determine whether a cycle exists in a singly linked list? How do you determine whether two singly linked lists intersect? If they intersect, how do you find the intersection point?

Approach

First Thoughts

Detecting a cycle: traverse the list. If there is no cycle you will reach NULL; if there is a cycle you will reach head.
Detecting intersection: a singly linked list has only one next field, so intersection must be one of two cases: “both have no cycle” or “one has a cycle and the other does not.”
Where were these first thoughts inadequate? After thinking over the following days, I gradually realized where the flaws were…

Revised Approach

First, move away from the intuitive “go by feel” approach. Although intuition makes it easy to understand, we still need to define the concepts of “containing a cycle” and “intersecting.”

If the ADT of a singly linked list were strictly followed, cycles and intersections would not occur. This is because pointers represent the logical order between elements, and the ADT has no logical relationship of a tail node pointing to another node. Therefore, the “singly linked list” considered here should only refer to a data structure whose nodes have a data field and a next field.

Containing a cycle: if the next field of some node in the list still points to a node in the same list, the list is said to contain a cycle.

Intersecting: if starting from L1 one can reach a node in L2, then L1 and L2 are said to intersect.

The first flaw I noticed: if the list contains a cycle, traversing it does not necessarily reach head, and usually will not, because a list with a cycle is in fact divided into two parts—outside the cycle and inside the cycle—and head can only be in the part outside the cycle. Also, rashly “traversing” the list in the same way as before is dangerous, because for a list with a cycle, using the usual traversal method only causes infinite recursion.

Also, once my understanding of intersection deepened, I realized that the previously understood case of “one with a cycle and one without” is not truly “one with a cycle and one without.” In fact, if two lists intersect and one has a cycle, the other will necessarily reach that cycle, which means “both contain a cycle” necessarily follows. If one list has a cycle and the other does not, they definitely do not intersect.

Furthermore, whether lists intersect can be divided into seven cases.

Implementation and Solution

Predefinitions:

First, define the data structure:

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

The functions we need to implement include:

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

The cycle-detection function was initially written to return a bool, where 1 means there is a cycle. But during the subsequent implementation of IfCross, I gradually realized that the position of the point where the cycle begins is quite important. So IfCircle was written as a function that returns an address value.

Why is IfCross’s implementation said to depend on the cycle-entry point? Among its seven cases:

(two cases) For those without a cycle, the intersection can be found, or confirmed absent, using the usual traversal method;

(one case) one with a cycle and one without—there is necessarily no intersection;

Both containing a cycle:

  • “Lists fully overlap” and “lists are completely unrelated”: relatively easy to implement directly through checks;

  • The most troublesome last two, “intersecting inside the cycle” and “intersecting outside the cycle”: if they intersect inside the cycle, the two intersection points are the cycle-entry points of the two lists; if they intersect outside the cycle, the cycle-entry point is also needed to constrain the traversal condition, so that the usual traversal method can be used.

An Important Tool: Fast and Slow Pointers

Since the usual traversal method no longer applies, how should we traverse the list? A good approach is to introduce [[fast and slow pointers]]. To visit every node, we can require that each time the fast pointer advances one step, a node is visited once. From the exit condition, setting the fast pointer’s speed to 2 and the slow pointer’s speed to 1 means the fast pointer strictly advances by 1 relative to the slow pointer each time; since the cycle length is finite, exit is guaranteed. More generally, the slow and fast speeds need not be 1 and 2. Given a cycle length L, we only require that (fast pointer speed - slow pointer speed) is coprime with L. The proof is given later.

Traversal via fast and slow pointers was initially written inside the IfCircle function, but later in the implementation I found it was used often, so I wrote it as a separate function.

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;
}
}

Properties of Traversing a Cyclic List with Fast and Slow Pointers

Proof Regarding the Choice of Fast and Slow Pointer Speeds

First, as long as every small step of the fast pointer (f = f->next) is accompanied by a visit, every element is visited at least once, so the requirement of “traversal” is easily satisfied. The main thing to consider is how to choose values that satisfy the traversal exit condition (f == s).

Obviously, regardless of the list structure, within finitely many steps both the fast and slow pointers will enter the cycle. So we only need to consider whether, when both are inside the cycle (with uncertain initial positions), the fast pointer will necessarily catch up with the slow pointer. This problem is equivalent to: with the slow pointer stationary and the fast pointer moving at speed (fast - slow), will it necessarily reach the slow pointer? Since the initial relative position is uncertain, the only way to satisfy “will necessarily reach the slow pointer” is that “the fast pointer can reach every node in the cycle within finitely many steps.” Thus the problem can be abstracted as follows:

Let the fast pointer’s speed be $f$, the slow pointer’s speed be $s$, and the cycle length be $L_c$; then the fast pointer’s relative speed is $v = f - s$. We have

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

where as $i$ ranges from $0$ to $L_c - 1$, $b_i$ should also run through $\{0, 1, \dots , L_c - 1\}$. Find $v$ satisfying this condition.

(Solution 1) Using $Bezout$’s theorem, as long as $\gcd(v , L_c) = 1$, then $\exists c_1, c_2$, s.t.$c_1 v + c_2 L_c = 1.$, adding $L_c v +(-v)L_c = 0$ to the above equation, we necessarily obtain $$c_1’ v = 1 + c_2’ L_c.(c_1 > 0)$$ and thus all values from $0$ to $L_c-1$ can be taken.

(Solution 2) Using an important property:

$(a,m)=1, \forall b \in \mathbb{Z}, ax\equiv b\pmod m$, and $ax\equiv b\pmod m$ has a unique solution modulo $m$. In this case, if we consider $b\in\{0,1,\dots,m-1\}, x\in \{0,1,\dots,m-1\}$, then $b$ and $x$ form a bijection.

(Proof) Suppose it is not a one-to-one mapping; then necessarily $$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}. $$

Then we have $$(x_1 - x_2) a = (k_1 - k_2) m.$$

Since $\gcd (a,m) = 1$, necessarily $$m\mid (x_1 - x_2).$$

But we know $ x_1\not= x_2\in{0,1,\dots,m-1} $, so a contradiction arises.

Therefore it necessarily forms a one-to-one mapping.

Then from the above property we have $$iv\equiv b_i\pmod{L_c}.$$

where $i\in\{0,1,\dots,L_c-1\}, b\in\{0,1,\dots,L_c-1\}$, and $i$ and $b_i$ form a bijection, so all values can necessarily be taken.

Properties Exhibited When the Speeds Are 2 and 1

Since we only need the speed difference to be coprime with the cycle length, and the cycle length is uncertain, we can only set the speed difference to 1. We may as well choose the most convenient values to implement: fast pointer speed 2, slow pointer speed 1.

We want the IfCircle function to return the address of the cycle-entry point, which took considerable effort. For a general list with a cycle, assume the length of the part outside the cycle is $L_0$ and the cycle length is $L_c$. When traversal with fast and slow pointers ends, the total distances traveled by the fast and slow pointers are $L_f$ and $L_s$ respectively. Also assume that at the moment the slow pointer enters the cycle, the distance it would need to catch up to the fast pointer’s position at that time is $L_{fs}$. Next, we examine the relationships among these quantities.

A basic property: since the fast pointer f has step length 2 and the slow pointer s has step length 1, it is easy to see that $$L_f = 2L_s.$$

Since the distance between s and the fast pointer when s enters the cycle is $L_{fs}$, the distance f should subsequently travel relative to s is $L_c - L_{fs}$, and the distance traveled relative to s equals the absolute distance s travels, so:

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

And from departure to meeting, the fast pointer, compared with the slow pointer, in fact only goes around the cycle a few more times. Thus:

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

Also, since s has traveled $L_0$ when it enters the cycle, f should have traveled $2L_0$ at that point—that is, it walked a distance of $L_0$ inside the cycle to reach $L_{fs}$—so:

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

Combining the above equations gives:

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

This is a very nice property: the absolute distance the slow pointer travels from departure to meeting is an integer multiple of the cycle length.

At this point, everything derivable from the quantities we can obtain, $L_f$ and $L_s$, is exhausted; many unknowns remain and require further investigation. We now note that f and s necessarily meet inside the cycle. If we start from their meeting point and traverse again with fast and slow pointers, then $L_0’ = 0, L_{fs} = 0$, so $$L_s’ = L_c.$$ Thus we obtain the cycle length by traversing the nodes inside the cycle, and can further obtain the value of $n$.

But if we continue manipulating the equations above, we find that $L_0 - L_{fs}$ is always eliminated or solved for as a whole. However, what we really need is one of them, so that we can find the address of the cycle-entry point. In fact, as shown in the figure below, what we need now is a more precise relationship between $L_0$ and $L_{fs}$—that is, based on the congruence, exactly how many $L_c$ they differ by.

Properties of the endpoint (meeting point) of Traverse(head)

The information here is implicit in the following: after s enters the cycle, f travels $L_c - L_{fs}$ relative to s, so the absolute distance f travels should be $2(L_c - L_{fs})$. The distance f travels before s enters the cycle is:

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

We also know the distance f travels after s enters the cycle, and the total distance f travels:

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

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

Combining them gives:

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

Then the congruence $L_0 \equiv L_{fs} \pmod {L_c}$ has a more precise expression:

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

Now we can find the address of the cycle-entry point: just let pointer p start from head and walk $(n-2)L_c$ first, and let pointer q be at the meeting point of Traverse(head). Then the distances from p and q to the cycle-entry point are both $L_{fs}$, and both face the cycle-entry point. Just advance them with the same step length, and the meeting point is the cycle-entry point.

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;
}

Then, with the help of IfCircle, which can return the cycle-entry point, IfCross can be implemented fairly conveniently:

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