每日一题---OJ题: 环形链表

片头

嗨! 小伙伴们,大家好! 今天我们来讲讲这道OJ题----环形链表,准备好了吗? 我们开始咯!

题目似乎有点抽象,我们举几个例子哈

上图中,总共有4个结点,分别为 3, 2, 0, -4, 链表中有一个环,尾结点连接到第二个结点。

上图中,总共有2个结点,分别为 1, 2, 链表中有一个环, 尾结点连接到第一个结点。

上图中,链表没有环。

所以，我们解决这道题的关键，就是判断这个链表有没有环

这里，我们提供一种思路

思路一：定义2个指针，分别为快指针和慢指针，假设慢指针每次走1步，快指针每次走2步。当它们相遇时，一定是出现了环，如果快慢指针没有相遇，那么链表中就没有环。

思路分析： slow指针走1步,fast指针走2步,一定可以追上吗? 会不会追不上?

当slow指针走到中间的时候,fast指针开始进环

当slow指针开始进环的时候,fast指针在环中可能已经走了n圈了

因为slow指针和fast指针都在环里面,slow指针进环以后开始追击。假设此时fast指针和slow指针之间的距离为N , 每追击一次,它们之间的距离缩小一步。

追击过程中, fast 和 slow 之间的距离变化

第0次: N

第1次: N-1

第2次: N-2

第3次: N-3

.........

第 n-2 次: 2

第 n-1 次: 1

第 n 次: 0 ---> 追上了

通过表格，我们可以发现，当 fast 和 slow 之间的速度只相差1个单位的时候,（比如： fast一次走2步, slow一次走1步 ; fast一次走3步, slow一次走2步 ; fast一次走4步, slow一次走3步）不管它们之间的距离是奇数还是偶数, fast 都可以追上 slow。由此，我们就可以推断出一个结论: 前提是fast和slow之间只相差1个单位, 当fast追上slow的时候, 链表中一定有环; 如果fast已经为空,或者fast的next指针为空, 那么链表中无环。

好滴，思路分析清楚了，那我们就要开始写代码啦！

等等，循环条件是啥嘞？想想看，如果单链表里面没有环，是不是fast指针最终为指向空或者 fast的next指针指向空呢? 为什么会有两个条件呢?因为要分奇数个结点和偶数个结点呀!

(注意: 当单链表有奇数个结点并且链表中无环时, fast的next会先走到NULL ; 当单链表有偶数个结点并且链表中无环时, fast会先走到NULL)

好啦,这道题的代码如下:

 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
        ListNode* fast = head;  //fast指针指向头结点
        ListNode* slow = head;  //slow指针指向头结点

        while(fast && fast->next)//当fast为空或者fast->next为空,就跳出循环
        {
            fast = fast->next->next;//fast走2步
            slow = slow->next;      //slow走1步
            if(slow == fast){       //如果fast和slow相交,证明存在环
                return true;
            }
        }
        return false;               //如果fast走到空了,说明链表无环
}

拓展部分:

slow走1步,fast走3步,一定能追上吗?

fast先进环,过一会儿,slow也会进环,假设这时fast和slow之间的距离为N,每追击一次,它们之间的距离缩小2步。

追击过程中，fast和slow之间的距离变化
N为偶数	N为奇数
第一次: N	第一次: N
第二次: N-2	第二次: N-2
第三次: N-4	第三次: N-4
第四次: N-6	第四次: N-6
...........	.............
第 n-2 次: 4	第 n-2 次: 3
第 n-1 次: 2	第 n-1 次: 1
第 n 次: 0 -->追上了	第 n 次: -1 -->意味着它们错过了,但是因为在环里面,相当于进入新一轮的追击,它们之间的距离变成了 C-1 (假设C为环的长度)