题目描述

题目链接：141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

例子

例子 1

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

例子 2

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

例子 3

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

Follow Up

Can you solve it using O(1) (i.e. constant) memory?

Constraints

• The number of the nodes in the list is in the range [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

解题思路

这道题首先需要想要要用快慢指针的思路来解，通过前后一快一慢两个指针迭代（快指针每次前进两步，慢指针每次前进一步）。假设链表中有存在闭环（即指针永远不会指向末尾），那么快指针总是会重新追上慢指针，这里有可能有人会觉得快指针在要追上慢指针时可能会直接跨过去而不是指向它，可以这么证明：

• 假设快指针距离慢指针只剩一步或者两步（假设是三步的话，下一次迭代之后距离会变为两步因此可以归为这一类）
• 假设只剩一步，那么下一次迭代，快慢指针会重合
• 假设只剩两步，那么下一次迭代之后会只剩一步，因此再下一次迭代还是会重合

因此假设存在闭环，快指针和慢指针要相遇的时候肯定是先重合再分开。

代码如下：

class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) return true;
        }

        return false;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 141.LinkedListCycle.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions