题目

https://leetcode.com/problems/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.

Example 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).

Example 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.

Example 3:

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

Constraints:

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

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

思路

读完题第一个思路就是把经过的所有节点的内存地址都存到一个哈希表中，然后每到一个节点就检查当前节点的地址是否在哈希表之中。但是这种解法缺点非常明显。第一是慢：虽然哈希表的查找时间复杂度近乎是O(1)，但是每次都这样查找实际上积累起来时间就长了。第二是消耗内存空间多：如果用一个哈希表把所有节点地址都存起来的话空间复杂度就是O(n)，而题中有一个深入问题是用O(1)的时间复杂度解决这个问题。对于这样判断链表里面是否有环，是否是回文等问题，我们可以使用快慢指针算法。

解法

解法1 – 快慢指针算法

我们声明两个指针，让他们一开始都指向head。

每次循环，我们让slow移动到下一个位置，而fast移动到下下个位置。

这样一直循环，如果快指针或者快指针的下一个节点为null，那么就说明没有环。如果循环到两个指针相等，那么说明链表有环。

bool hasCycle(struct ListNode *head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}

解法2（脏解法） – 改变原链表的值以标记走过

这个方法很脏，因为他改变了原链表的值。

我们读过题干会发现：

-105 <= Node.val <= 105

于是我们可以改变原链表的值为一个大于10e5的数或小于-10e5的数，每次经过一个节点都检查当前节点是否等于那个数。如果直到遇到null都不等于那个数说明没有环，反之有环。

bool hasCycle(struct ListNode *head) {
    while (head && (head->val != 10e6)) {
        head -> val = 10e6;
        head = head->next;
    }
    return head;
}