【一起刷题】环形链表

环形链表

力扣141-环形链表

题目描述

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

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

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


提示：

1. 链表中节点的数目范围是 [0, 104]
2. -10⁵ <= Node.val <= 10⁵
3. pos 为 -1 或者链表中的一个 有效索引 。

要求：空间复杂度为O(1)

实现思路

采用快慢指针解决问题，快指针一次走两步，慢指针一次走一步

快指针走两步的原因：
设环的开始节点为startNode
设环长度为C；链表在环开始之前的长度为L；当慢指针slow走到startNode时，快指针fast已经走过startNode的距离为N(N fast和slow之间的距离为C-N，要想准确的使两指针相遇，走的步数只能是C-N的因子，而这个差值与具体题目有关，不好确定，
因此我们选择快慢指针速度差为1，当slow进入环时，再进行C-N次循环，两指针就能相遇

假如快指针走三步，慢指针走一步，此时速度差是2
当C-N是偶数时，第一圈可以相遇
当C-N不是偶数时，第一圈两指针的距离为C-N，C-N-2，…，1，-1，即fast在slow前一个，此时两指针之间距离为C-1，当C-1为偶数时两指针可以相遇，C-1为奇数时两指针则会一直循环走下去，永不可能相遇
同理，当两指针速度差是3时，
当C-N是3的倍数时，第一圈可以相遇
当C-N不是3的倍数时，最终两指针的距离为-1或-2
-1：fast在slow前一个，两指针距离为C-1，当C-1为3的倍数时可以相遇，同样，不是3的倍数需要再讨论。
-2：fast在slow前两个，两指针距离为C-2，当C-2为3的倍数时可以相遇，同样，不是3的倍数需要再讨论。。
综上所述，采用快慢指针速度差为1的方案。

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    // 快慢指针
    struct ListNode *fast = head,*slow = head;
    while(fast&&fast->next){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow){
            return true;
        }
    }
    // 链表结尾指向空，没有环
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20