141. 环形链表

题目要求

给你一个链表的头节点head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回true。 否则，返回false。

示例 1：

输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1输出：false解释：链表中没有环。

提示：

• 链表中节点的数目范围是[0, 104]
• -105 <= Node.val <= 105
• pos为-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_set<ListNode*>seen; //遍历链表 while(head!=NULL) { //如果找到了重复节点,则有环 if(seen.find(head)!=seen.end()) { return true; } else { seen.insert(head); head=head->next; } } return false; } };

详细解释

第 1 行：创建 “门牌号登记本”

unordered_set<ListNode*>seen;

翻译：准备一本叫seen的登记本，这本本子只记小房子的门牌号，而且同一个门牌号只能记一次（重复记会被拒绝），查起来还特别快。
类比：您出门逛小区，带了一本空白的登记本，专门记走过的房子门牌号，防止绕圈。
第 2 行：开始 “逛小区” 的循环

while(head!=NULL)

while：只要满足条件，就一直重复做后面的事（循环）；
head!=NULL：条件是 “当前要逛的房子门牌号不是空的”（还有房子可逛）；
翻译：从第一个房子（head）开始，只要脚下还有路（能找到下一个房子），就一直逛。
类比：您从小区第一个房子出发，只要还能看到下一个房子的门牌号，就继续走。
第 3-8 行：检查当前房子是不是 “逛过了”（核心判断）

if(seen.find(head)!=seen.end()) { return true; }

if：做一个判断，满足条件就执行大括号里的事；
seen.find(head)：拿着当前房子的门牌号（head），翻seen登记本找这个号；
!=seen.end()：“不等于登记本的封底”—— 意思是 “找到了这个门牌号”（end()是 “没找到” 的标记，不是本子末尾）；
return true;：找到重复门牌号了，说明绕圈了（有环），直接告诉外面 “有环！” 并结束函数。
类比：您走到一个房子门口，翻登记本一看，这个门牌号之前记过→说明您绕回老地方了，喊一声 “小区绕圈啦！” 就回家。
第 9-13 行：没逛过就 “登记门牌号，继续逛”

else { seen.insert(head); head=head->next; }

else：如果上面的判断不成立（没找到重复门牌号），就做这些事；
seen.insert(head)：把当前房子的门牌号写进登记本；
head=head->next;：取下一个房子的门牌号（当前房子门口贴的next），准备逛下一个。
类比：您看登记本，这个门牌号没记过→把它写进本子，然后按门口贴的下一个门牌号，走到下一个房子。
第 14 行：逛完所有房子，没绕圈

return false;

翻译：能走出上面的while循环，说明head==NULL（走到了小区尽头，没有下一个房子了），而且全程没找到重复门牌号→链表没环，告诉外面 “没绕圈！”。
类比：您把小区所有房子都逛完了，走到了路的尽头，登记本里也没有重复的门牌号→小区是直的，没有绕圈的路