code deep_
创建时间: 2025-04-21最后更新: 2025-12-22作者: yangbo(96862973d)

环形链表

环形链表是另一种形式的链式存储结构. 它的特点是链表中最后一个结点的指针域指向头结点, 整个链表形成一个环.

由于环形链表的末尾节点指向头节点, 因此, 我们可以仅使用一个指针来存储链表地址, 而不需要使用两个指针.

例如, 在 React 中, useState 的 Hook 就是基于环形链表实现的. 当有多个更新任务时, 会有一个 queue.pending 指针来指向环形链表的末尾节点, 如下所示.

通过这样的方式, 我们可以通过末尾节点快速访问首节点

code.ts
1
// 尾部节点 

2
tail = queue.pending

3
// 首节点

4
head = queue.pending.next

在末尾添加一个节点

代码如下

code.ts
01
// 创建新节点

02
const update = {

03
  next: null,

04
  action: () => {}

05
}

06


07
// 将新节点添加到末尾

08
const tail = queue.pending // 尾部节点

09
const head = queue.pending.next // 首节点

10


11
// 将新节点添加到尾部

12
tail.next = update

13
update.next = head

14
queue.pending = update

图例演示如下

创建一个新节点

让老的尾部节点指向新节点

让新节点指向首节点

让 queue.pending 指向新节点

遍历循环链表

循环链表的遍历需要特殊处理一下, 一不小心可能会陷入无限循环当中, 因此, 我们要巧妙的设计一个缓存指针, 来记录当前遍历到的节点. 如果该节点与循环开始的节点相同, 则推出循环.

代码如下

code.ts
1
let current = queue.pending

2


3
while (true) {

4
  current = current.next

5
  if (current === queue.pending) {

6
    break

7
  }

8
}

如果我们已知链表的长度, 也可以使用 for 循环来遍历链表.

code.ts
1
for (let i = 0; i < length; i++) {

2
  current = current.next

3
}

练习题：判断链表中是否存在环

原题地址：141. 环形链表

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

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

如果链表中存在环 , 则返回 true . 否则, 返回 false .

示例 1

code.ts
1
输入：head = [3,2,0,-4], pos = 1

2
输出：true

3
解释：链表中有一个环, 其尾部连接到第二个节点.

示例 2

code.ts
1
输入：head = [1,2], pos = 0

2
输出：true

3
解释：链表中有一个环, 其尾部连接到第一个节点.

示例 3

code.ts
1
输入：head = [1], pos = -1

2
输出：false

3
解释：链表中没有环.

解题思路：20250422
专栏首页
到顶
专栏目录