环形链表的判定与其拓展延伸

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-le3xMBJl-1690429929886)(https://img-home.csdnimg.cn/images/20220524100510.png#pic_center)]

💓问题：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

来源：力扣（LeetCode）

图解：

在这里插入图片描述

代码展示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        return true;
    }
      return false;
}

拓展延伸：

其实这就像是 高中物理题 的追击相遇问题

和两个指针之间的距离与每回两个指针之间缩减的距离密切相关。

那会有同学想怎么确定fast 一定会追上slow 指针呢，他两个一定会在环里相遇呢？ 其实这是一个推理证明题， 我们先来看结论

slow走一步 ，fast 走两步 fast 一定会追上slow

我们简单来推理一下 当slow 也进入环之后，fast 也就开始追了。 假设一下，这时候两个指针之间的距离是N 再追的过程·当中，两个指针的距离每次都会缩小一 N N-1 N-2 N-3 … … 3 2 1 0 当距离N为0 的时候就会追上了。所以一定就会追上。

那么当slow 走一步，fast 走三步 会不会·追上·呢？

假设两个指针之间距离还是N，每回两者之间的距离会减少2 ，所以 N N-2 N-4 N-6 … … 最后不一定会是0； 有可能会是一个负数， 那么当出现负数的时候就证明已经错过了。

在这里插入图片描述

如此图所示：

slow与fast 之间的距离为5 ，也就是N=5 每次两个指针之间的距离减2 最后成-1了 也就是下面图所示，fast 把slow 超过去了，两个指针并不相等。

在这里插入图片描述

所以就会继续进行指针移动，直到有一天 ，两个指针正好指向了同一个位置，相等了才会停下来。

要不然就是一个死循环，一直不会结束。

所以得到结论：

当slow 走一步，fast 走三步 ，不确定，有可能会追上正好相等，也有可能是一个死循环。

那么同理就可以证明slow 走一步，fast 走四步的 时候呢？

有兴趣的同学可以自行研究一下。