题解 | #判断链表中是否有环#

题目主要信息:

给定一个链表的头节点，判断这个链表是否有环
环形链表如下所示：

具体思路:

我们都知道链表不像二叉树，每个节点只有一个val值和一个next指针，也就是说一个节点只能有一个指针指向下一个节点，不能有两个指针，那这时我们就可以说一个性质：环形链表的环一定在末尾，末尾没有NULL了。为什么这样说呢？仔细看上图，在环2，0，-4中，没有任何一个节点可以指针指出环，它们只能在环内不断循环，因此环后面不可能还有一条尾巴。如果是普通线形链表末尾一定有NULL，那我们可以根据链表中是否有NULL判断是不是有环。

但是，环形链表遍历过程中会不断循环，线形链表遍历到NULL结束了，但是环形链表何时能结束呢？我们可以用一种双指针技巧，这也是处理环形链表常用的技巧：

step 1：设置快慢两个指针，初始都指向链表头。
step 2：遍历链表，快指针每次走两步，慢指针每次走一步。
step 3：如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL。
step 4：如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。

双指针过程可以参考如下图示：

alt

代码实现:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL) //先判断链表为空的情况
            return false;
        ListNode* fast = head; //快慢双指针
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){ //如果没环快指针会先到链表尾
            fast = fast->next->next; //快指针移动两步
            slow = slow->next; //慢指针移动一步
            if(fast == slow) //相遇则有环
                return true;
        }
        return false; //到末尾则没有环
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下遍历链表 $n$ 个节点
空间复杂度： $O (1)$ ，仅使用了两个指针，没有额外辅助空间