算法7（力扣141）-循环链表

张春 · 2025-1-23 15:04:10

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

x

1、问题

         给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过一连跟踪 next 指针再次到达，则链表中存在环。为了体现给定链表中的环，评测系统内部利用整数 pos 来体现链表尾连接到链表中的位置（索引从 0 开始）。留意：pos 不作为参数进行通报
仅仅是为了标识链表的实际环境。
如果链表中存在环，则返回 true 。否则，返回 false
2、采用例子

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

先创建循环链表
4、具体步骤

（1）定义链表结构（由于此次需要利用数组创建链表，以是定义链表结构需要给next一个默认值null）

（2）创建循环链表

实现思路：找到开始循环的节点，将链表循环的最后一位指向开始循环的节点

1）通过通报数组长度是否为空，判断链表是否为空链表，空链表直接返回

2）定义链表头结点、当前节点和开始循环的节点

3）通过循环遍历赋值，同时探求开始循环的节点（给的有开始循环的位置pos）

4）循环结束后，让链表的最后一个循环点指向开始循环的点

5）打印并返回链表

（3）检查是否有循环

通过快慢指针，当快指针追上慢指针时，即存在循环

1）判断是否是空链表，空链表返回

2）进入函数，定义快慢指针，判断是否有循环，存在返回true

3）函数结束，无循环返回false

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 = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
</p>
<script>
class ListNode{
constructor(val,next=null){
this.val = val
this.next = next
}
}
let arr = [3, 2, 0, -4]
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[0])
// 当前节点
let cur = head
// 开始循环的节点
let cycleNode = null
for (let i = 1; i < arr.length; i++) {
// 利用数组的值创建节点，赋值给当前节点
cur.next = new ListNode(arr[i])
// 指针后移
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企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

算法7（力扣141）-循环链表

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块