Leetcode 141.环形链表

题目描述：

给定一个链表，判断链表中是否有环。

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

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

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 $[0, 10^4]$
• $-10^5 <= Node.val <= 10^5$
• pos 为 -1 或者链表中的一个 有效索引 。

链接：

https://leetcode-cn.com/problems/linked-list-cycle

题目分析

  这道题也是一个典型的题目，可以使用快慢指针解决。我们知道，如果链表中存在环，则按照链表的顺序走，最终会在环里面一直转圈。所以如果按照链表顺序走能够走到终点（走到 nullptr）则说明链表不存在环。而如果我们使用两个指针同时在链表中行走，快指针一次走两步，而慢指针一次走一步，则如果存在环，快指针会比慢指针先进入环中并开始转圈，当慢指针也进入环后，它们会在环中的某一个节点相遇，此时快指针“套”了慢指针若干圈。（为什么一定会相遇？因为它们的速度差是 1，则每一次前进，它们之间的步数差增加 1，而当它们同时处于环中并且步数差是环长的整数倍时，它们就相遇了）因此如果快慢指针相遇，则说明存在环。
  一些细节：快指针一次走两步，在走之前需要判断 fast 和 fast->next 是否为空，避免非法访问。为空时其实也说明不存在环，可以直接返回 false。出发时，快指针在 head->next 而慢指针在 head，这是由于我们循环的终止条件是两个指针相遇，如果它们的出发点是相同的则不会进入循环。其实我们也可以理解为它们是在 head 之前才是起跑线，第一次行走时慢指针到 head 而快指针已经到了 head->next，如果使用一个 do-while 循环则可以从 head 起跑。由于它们在同一位置起跑，如果链表不存在环，则快指针一定先于慢指针到达终点，因此退出条件只设置快指针即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode *fast = head->next;
        ListNode *slow = head;
        while(fast != slow){
            if(fast == nullptr || fast->next == nullptr) return false;
            fast = fast->next->next;
            slow = slow->next;
        }
        return true;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为链表的长度。当不存在环时，快指针到达终点就结束，每个结点至多被访问两次；当存在环时，至多行走了 $n$ 步慢指针就会进入环，而两个指针都进入环之后，至多行走 $n$ 步快慢指针就会相遇。因此复杂度都是 $O(n)$。
  空间复杂度：$O(1)$。我们只需要两个指针的空间。