leetcode hot100 之 环形链表

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

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。这里 pos 只是说明链表存在环，且链表末尾连接到链表第 pos 的节点。

原题链接：https://leetcode-cn.com/problems/linked-list-cycle/

快慢指针法。慢指针走一步，快指针走两步。那么慢指针走一圈时，快指针走两圈。也就是慢指针和快指针的距离最大为一圈，且两者每走一次，两者距离缩小一步。一圈最多为n，所以最多走 n 次。复杂度为O(n)
如果快指针走完链表，遇到 NULL了，那就说明没有环了。

• 复杂度分析
  • 时间复杂度 O(n)。
  • 空间复杂度 O(1)。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) {
            return false;
        }
        ListNode* preHead = new ListNode();
        preHead->next = head;
        ListNode* fast = preHead;
        ListNode* slow = preHead;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
};