讲解LeetCode第141题：环形链表（完整代码）
讲解LeetCode第141题：环形链表（完整代码）
序属秋秋秋
发布于 2025-12-18 14:52:03
发布于 2025-12-18 14:52:03
讲解LeetCode第141题：环形链表
方法一：哈希表
完整代码展示
//环形链表——哈希表
#include <iostream>
#include <unordered_set>
using namespace std;
struct ListNode
{
int date;
ListNode* next;
ListNode(int val) :date(val), next(nullptr) {}
};
class Solution
{
public:
bool hasCycle(ListNode* head)
{
unordered_set <ListNode*>seen;
while (head != nullptr)
{
if (seen.count(head) > 0)
{
return true;
}
seen.insert(head);
head = head->next;
}
return false;
}
void destroyList(ListNode* head)
{
while (head!=nullptr)
{
ListNode* curr = head;
head = head->next;
delete curr;
}
}
};
int main()
{
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(4);
head->next->next->next->next = head->next;
Solution judge;
bool result = judge.hasCycle(head);
if (result)
{
cout << "这个链表是环形链表" << endl;
}
else
{
cout << "这个链表不是环形链表" << endl;
}
judge.destroyList(head);
return 0;
}核心原理演示
在这里插入图片描述
代码片段解释
片段一：
ListNode(int val) :date(val), next(nullptr) {}
ListNode(int val) :date(val), next(nullptr) {}：是一个用于初始化链表节点的构造函数。ListNode(int val)：是构造函数的声明部分，它表示这是一个名为ListNode的构造函数，它接受一个int类型的参数valdate(val), next(nullptr)：是初始化列表，它紧跟在构造函数的参数列表之后（两者之间用冒号:分隔）
date(val)：这表示将成员变量date初始化为构造函数参数val的值next(nullptr)：这表示将成员变量next初始化为nullptr（nullptr是一个空指针），即这个节点当前是链表的尾节点，不指向任何其他节点。
成员初始化列表：它直接在对象构造时初始化成员变量，在构造函数体执行之前初始化成员变量，而不是在构造函数体内赋值。
片段二：
if (seen.count(head) > 0)
seen.insert(head);
seen.count(head)用于检查head指针是否已经在seen集合中，即检查当前节点是否已经被访问过。
- 如果head已在集合中，count方法将返回1
- 如果head不在集合中，count方法将返回0
即，如果head已经在集合中，说明链表存在环，因为节点被重复访问了。
seen.insert(head)用于将head指针添加到seen集合中，即将当前节点标记为已访问。
方法二：快慢指针（龟兔赛跑算法）
完整代码展示
//环形链表——快慢指针
#include<iostream>
using namespace std;
struct ListNode
{
int date;
ListNode* next;
ListNode(int val) :date(val), next(nullptr) {}
};
class Solution
{
public:
bool hasCycle(ListNode* head)
{
if (head != nullptr&&head->next!=nullptr)
{
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast)
{
slow = slow->next;
fast = fast->next->next;
if (fast == nullptr || fast->next == nullptr)
{
return false;
}
}
return true;
}
}
void destroyList(ListNode* head)
{
while (head != nullptr)
{
ListNode* curr = head;
head = head->next;
delete curr;
}
}
};
int main()
{
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(4);
head->next->next->next->next = head->next;
Solution judge;
bool result = judge.hasCycle(head);
if (result)
{
cout << "这个链表是环形链表" << endl;
}
else
{
cout << "这个链表不是环形链表" << endl;
}
judge.destroyList(head);
return 0;
}核心原理演示
在这里插入图片描述
代码片段解释
片段一：
ListNode* slow = head;
ListNode* fast = head->next;为什么我们要规定初始时慢指针在位置head，快指针在位置head->next，而不是两个指针都在位置head？
- 观察代码，我们使用的是 while循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始化都置于 head那么 while 循环就不会执行。 因此，我们可以假想在 head之前有一个虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head->next，这样我们就可以使 while循环了。
- 当然，我们也可以使用 do-while循环，此时，我们就可以把快慢指针的初始值都置为 head
片段二：
if (fast == nullptr || fast->next == nullptr)循环的终止条件为什么要写成fast == nullptr || fast->next == nullptr这样？
在这里插入图片描述
出现这两种情况都说明该链表不是环形链表，所以执行return false;
疑问：兔子（fast指针）会不会跳过乌龟（slow指针），从来不会与乌龟相遇呢？
这是不可能的因为如果有环的话，那么兔子和乌龟早晚都是会进入环中的， 这时用“相对速度”思考，相当于乌龟不动，兔子相对于乌龟每次只走一步，这样就可以看出：
- 有环的话它俩一定会相遇。
- 没环的话它俩一定不会相遇。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
