[数据结构与算法]2021.9.17 力扣-环形链表

题目描述：

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

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

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

进阶：

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

方法一：

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

利用双指针法，每次循环时都将left->right改成right->left，如果该链表中有环，那么最终一定会又回到head，否则说明链表中没有环

方法一的改进版：

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr) return head;
        ListNode* dummynode = new ListNode(0);
        ListNode* left = head;
        ListNode* right = head->next;
        while (right != nullptr)
        {
            if (right == dummynode)
            {
                return true;
            }
            left->next = dummynode;
            left = right;
            right = right->next;
        }
        return false;
    }
};

每次循环时让left指向一个不在链表中的结点dummynode，判断最终能否到达这个结点即可。原先的方法一，当链表中有环时还需再次走到链表的头部才能判断出来，而这个改进的版本则不用，可以提高不少时间效率。

方法二：

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

快慢指针做法，第一次使用，还是挺有趣的。官方的解释如下：

时间复杂度：O(N)，其中 NN 是链表中的节点数。

当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

空间复杂度：O(1)。我们只使用了两个指针的额外空间。