LeetCode141. Linked List Cycle（链表 / 模拟）

Easy
Accepted：385,781
Submissions：1,059,839

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

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

Example 2:

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

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

链接

https://leetcode.com/problems/linked-list-cycle

题意

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

题解

两种解法，一个是哈希，一个是快慢指针。

哈希的话，就相当于判断数组中是否有相同的数，我们判断的是链表中是否存在相同的结点，使用unordered_set存入链表结点，如果链表存在环，那么最后一个结点肯定会指向之前出现过的结点，时间复杂度$O(n)$，空间复杂度$O(n)$
使用快慢指针slow和fast，slow开始指向head，fast开始指向head->next，然后slow每次往前走一步，fast每次往前走两步，如果链表中存在环，那么slow和fast后面肯定会相遇，注意判断结点为空的情况，时间复杂度$O(n)$，空间复杂度$O(1)$

代码

Runtime: 12 ms, faster than 99.37% of C++ online submissions for Linked List Cycle.
Memory Usage: 9.7 MB, less than 64.15% of C++ online submissions for Linked List Cycle.

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

Runtime: 28 ms, faster than 5.32% of C++ online submissions for Linked List Cycle.
Memory Usage: 11.9 MB, less than 10.38% of C++ online submissions for Linked List Cycle.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return false;
        unordered_set<ListNode* > uset;
        while (head != NULL)
        {
            if (uset.find(head) != uset.end())
                return true;
            uset.insert(head);
            head = head->next;
        }
        return false;
    }
};

The end.
2019年4月15日星期一