找出链表中环的入口节点

前言

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


描述

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


思路

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

  这里先明确三个名称:

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

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

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

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

找出链表中环的入口节点_第1张图片

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

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

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,沿着链表前进,最后它们相遇的位置,就是环入口节


代码

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

你可能感兴趣的