2023-07-29每日一题
一、题目编号
141. 环形链表
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 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) {
int cnt = 0;
if(head == NULL){
return false;
}
while(head->next != NULL){
cnt++;
head = head->next;
if(cnt > 10001){
return true;
}
}
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) {
if(head == NULL || head->next == NULL){
return false;
}
ListNode *fast = head->next;
ListNode *slow = head;
while(fast->next != NULL){
if(fast == slow){
return true;
}
slow = slow->next;
fast = fast->next;
if(fast->next == NULL){
return false;
}
if(fast == slow){
return true;
}
fast = fast->next;
}
return false;
}
};
五、解题思路
(1) 因为我们知道链表的最大长度为104,所以我们最直接的做法就是指针尝试移动104 + 1次,如果能移动这么多次,那么一定会存在环。这是暴力的解法,在第一段代码中已经给出。文章来源:https://www.toymoban.com/news/detail-618551.html
(2) 使用快慢指针来解决问题,快指针每次向前面移动两下,慢指针每次向前移动一下,如果快指针追上慢指针,那么一定存在环,如果追不上(到达链表最后,那么一定不存在环)。文章来源地址https://www.toymoban.com/news/detail-618551.html
到了这里,关于2023-07-29 LeetCode每日一题(环形链表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!