141.环形链表(C++)

题目英文描述:
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.

题目中文描述：
给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

思路：1、hash存储访问过的地址。
2、双指针，一快一慢，快指针步长为2，慢指针步长为1，跟运动员跑圈类似，只要快指针追上慢指针，即代表链中存在环，若快指针到达NULL，则表示不存在环，该方法空间复杂度为O(1)。

代码（哈希）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*,bool> map;
        while(head) {
            if(map[head] == true) return true;
            map[head] = true;
            head = head->next;
        }    
        return false;
    }
};

代码（双指针）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next) { //fast步长为2，因此要判断下一个指针是否为空，否则空指针错误
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }    
        return false;
    }
};