算法7（力扣141）-循环链表
1、问题给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过一连跟踪 next 指针再次到达，则链表中存在环。 为了体现给定链表中的环，评测系统内部利用整数 pos 来体现链表尾连接到链表中的位置（索引从 0 开始）。留意：pos 不作为参数进行通报
仅仅是为了标识链表的实际环境。
如果链表中存在环 ，则返回 true 。 否则，返回 false
2、采用例子
输入：head = , pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
3、实现思路
先创建循环链表
4、具体步骤
（1）定义链表结构（由于此次需要利用数组创建链表，以是定义链表结构需要给next一个默认值null）
https://i-blog.csdnimg.cn/direct/d960ed57793e43f2877fe67376912448.png
（2）创建循环链表
实现思路：找到开始循环的节点，将链表循环的最后一位指向开始循环的节点
https://i-blog.csdnimg.cn/direct/452a76e596724bb3b11b1a7a32dc6f95.png
1）通过通报数组长度是否为空，判断链表是否为空链表，空链表直接返回
https://i-blog.csdnimg.cn/direct/b9c7c4b9af914adcb21ef72c2236d214.png
2）定义链表头结点、当前节点和开始循环的节点
https://i-blog.csdnimg.cn/direct/69f3b67df3b04ca0ae1a363ea41ac24e.png
3）通过循环遍历赋值，同时探求开始循环的节点（给的有开始循环的位置pos）
https://i-blog.csdnimg.cn/direct/b0a7aa7b5b4e4221a71a3b382d93abb3.png
4）循环结束后，让链表的最后一个循环点指向开始循环的点
https://i-blog.csdnimg.cn/direct/072e022d0e784df4a4909afa0e63de5a.png
5）打印并返回链表
https://i-blog.csdnimg.cn/direct/60af4b7dd1e2460a8cc1083765b49410.png
（3）检查是否有循环
通过快慢指针，当快指针追上慢指针时，即存在循环
https://i-blog.csdnimg.cn/direct/d04bb406fb0b400693f2698d2a6021c1.png
1）判断是否是空链表，空链表返回
https://i-blog.csdnimg.cn/direct/deff0be38414435698207c9eb9697530.png
2）进入函数，定义快慢指针，判断是否有循环，存在返回true
https://i-blog.csdnimg.cn/direct/288b78b4f43945c2b15ddc8f93f58bf9.png
3）函数结束，无循环返回false
https://i-blog.csdnimg.cn/direct/2f1848d4de584666b4ecb793c09d07b1.png
5、完整代码
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>环形链表</title>
</head>
<body>
<p>
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递
。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false
</p>
<p>
输入：head = , pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
</p>
<script>
class ListNode{
constructor(val,next=null){
this.val = val
this.next = next
}
}
let arr =
let pos = 1
let head = cycleList(arr,pos)
hasCycle(head)
// 怎么创建一个环形链表
function cycleList(arr,cycleStartIndex){
// 空数组，即链表为空
if (arr.length===0) {
return null
}
// 头结点
let head = new ListNode(arr)
// 当前节点
let cur = head
// 开始循环的节点
let cycleNode = null
for (let i = 1; i < arr.length; i++) {
// 利用数组的值创建节点，赋值给当前节点
cur.next = new ListNode(arr)
// 指针后移
cur = cur.next
// 判断循环点,是循环点，将当前节点赋值给循环点作为标记，方便后续构建闭环
if(i === cycleStartIndex){
cycleNode = cur
}
}
// 让循环结束时当前节点的下一位指向循环点，构成闭环
cur.next = cycleNode
console.log(head);
// 返回链表
return head
}
function hasCycle(head){
// 空链表
if (!head)return false;
// 使用快慢指针，当快指针和慢指针指向同一节点时存在环
let slow = head
let fast = head
while(fast&&fast.next){
fast = fast.next.next
slow = slow.next
if(fast == slow){
console.log(true);
return true
}
}
console.log(false);
return false
}
</script>
</body>
</html> 6、力扣通过代码
var hasCycle = function(head) {
// 空链表
if (!head)return false;
// 使用快慢指针，当快指针和慢指针指向同一节点时存在环
let slow = head
let fast = head
while(fast&&fast.next){
fast = fast.next.next
slow = slow.next
if(fast == slow){
console.log(true);
return true
}
}
console.log(false);
return false
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]