前言

  今天刷《剑指offer》的编程题，遇见一道挺有意思的题目，叫链表中环的入口节点，写篇博客记录一下。


描述

  给出一个链表，在这个链表中至多存在一个环，要求：若链表中有环，则返回环的入口节点，若没有环，返回null。


思路

  我们可以设置两个指针求解此问题：一个快指针fast，每次向前走两个节点，一个慢指针low，每次向前走一个节点；我们首先需要知道一个结论：这两个指针一快一慢向前走，若链表有环，则两个指针一定会相遇；

  这里先明确三个名称：

  • 头节点：表示链表的第一个节点；
  • 环入口节点：若链表中有环，则进入这个环的第一个节点；
  • 相遇点：快慢指针相遇的节点；

  我们设置三个变量来求解这个问题：

  • 变量a：头节点 到 环入口节点的距离；
  • 变量b：从环入口节点 沿链表方向前进到 相遇点的距离；
  • 变脸c：从相遇点 沿链表方向到 环入口节点的距离；

  所以，链表的长度 = a + b + c，而环的长度就是b+c；

  画个图，把上面说的变量和名称都标记上，我们不难看出，从开始到两个指针相遇，慢指针low走过的距离为a+b，而快指针fast走过的距离为a + k×(b+c) + b，其中k是一个整数，且k>0（因为如果k==0，那快慢指针走过的距离就相等了）；快指针fast每次前进两个节点，而慢指针low每次前进一个节点，所以我们可以得到一个结论：相同时间内，快指针的走的路程是慢指针的两倍；

  根据以上结论，我们可以得到一个公式：2×(a+b) == a + k × (b+c) + b，而这个公式可以进行化简，过程如下：

1
2
3
4
5
2×(a+b) == a + k × (b+c) + b;
2a + 2b == a + k × (b+c) + b;
a + b == k × (b+c);
a == k × (b+c) - b;
a == (k-1) × (b+c) + c;  // 最终结果

  经过一系列化简，我们可以得到a == (k-1) × (b+c) + c，而上面我们说过，(b+c)就是链表中环的长度，所以这个公式可以解释为：从链表头节点到环入口节点的距离，等于环长度的k-1倍，再加上从相遇点到环入口节点的距离；

  上面的解释说明了什么？说明：两个指针，一个从链表头节点沿着链表向前走，另一个从快慢指针相遇点沿着链表向前走，最后它们会在环入口节点相遇（这里要好好理解一下）；我们可以想象一下，指针在相遇点时，根据上面的最终结果，要向前走(k-1) × (b+c) + c这么长，而我们又知道，(b+c)就是环的长度，走一个b+c，就是饶了一圈，又回到了相遇点，所以当走完(k-1) × (b+c)，其实又回到了相遇点；而这时，我们还要再向前走c个单位，c我们在上面已经说过了，就是相遇点到环入口的距离，所以走完c，指针就到了环入口了；而a我们也说过了，它是头节点走到环入口的距离。所以，才有了上面的说明。

  所以，这道题目的求解步骤就出来了：设置一个快指针fast，每次向前走两个单位，设置一个慢指针low，每次向前走一个单位，当这两个指针相遇，到达相遇点时，我们将设立一个指针指向链表头节点，另一个指针指向相遇点，两个指针速度均为1，沿着链表前进，最后它们相遇的位置，就是环入口节。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public ListNode EntryNodeOfLoop(ListNode pHead) {
    if(pHead == null) {
        return null;
    }
    // 设置快慢指针，快指针一次走两步，慢指针一次走一步
    ListNode fast = pHead;
    ListNode low = pHead;
    do {
        // 快指针先走一步
        fast = fast.next;
        // 若fast为null，表示没环，直接return空
        if(fast == null) {
            return null;
        }
        // 若不为null，再向前走一步
        fast = fast.next;
        // 慢指针向前走一步
        low = low.next;
    }while(fast != null && fast != low);

    // low指针指向链表头节点，fast指针不变，还是在相遇点
    // 两个指针速度均为1，向前走，再次相遇的点就是环入口节点
    low = pHead;
    while(low != fast) {
        low = low.next;
        fast = fast.next;
    }
    return low;
}