34. 链表中环的入口结点

解法一

1. 时间复杂度：$O(n)$
2. 空间复杂度：$O(M)$ 取决于数值范围，如果用hash table，是$O(n)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    const int N = 100010;
    ListNode *entryNodeOfLoop(ListNode *head) {
        bool is_travel[N];
        for (ListNode *cur = head; cur; cur = cur->next)
        {
            if (!is_travel[cur->val])  is_travel[cur->val] = 1;
            else  return cur;
        }

        return NULL;

    }
};