142. 环形链表
哈希表
思路
这种解法通过哈希表，当成环时（即再次访问到之前访问过的元素时），可以判断是环，反之则不是。
代码实现
class Solution { public: ListNode *detectCycle(ListNode *head) { unordered_set<ListNode *> visited; while (head) { if (visited.count(head)) { return head; } visited.insert(head); head = head->next; } return NULL; } };
复杂度分析
时间复杂度：O ( N )，其中 N为链表中节点的数目。我们恰好需要访问链表中的每一个节点
空间复杂度：O ( N )，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中
快慢指针
思路
通过两个指针，分别叫 s l o w 和 f a s t，起始位置均在链表首部，f a s t前进 2 22 步，s l o w 前进 1 步。如果存在环路，两者必然会相遇。一次相遇后，由下图可知 x = z ，即从相遇点到入环点的距离，恰好等于从链表头部到入环点的距离。所以将 f a s t 指针移到链表头部，改为每次前进一步，下一次相遇一定在环首
借用网上的图 来源：LeetCode
代码
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *fast = head, *slow = head; do { if (!fast || !fast->next) { return NULL; } fast = fast->next->next; slow = slow->next; } while (fast != slow); fast = head; while (fast != slow) { fast = fast->next; slow = slow->next; } return fast; } };
复杂度分析
时间复杂度：O ( N )，其中 NN 为链表中节点的数目。在最初判断快慢指针是否相遇时，s l o w 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O ( N ) + O ( N ) = O ( N )
空间复杂度：O ( 1 )
