前端码易

环形链表

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

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

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

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

1
// 尾部节点 

2
tail = queue.pending

3
// 首节点

4
head = queue.pending.next

在末尾添加一个节点

代码如下

1
// 创建新节点

2
const update = {

3
  next: null,

4
  action: () => {}

5
}

6


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

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

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

10


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

12
tail.next = update

13
update.next = head

14
queue.pending = update

图例演示如下

创建一个新节点

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

让新节点指向首节点

让 queue.pending 指向新节点

遍历循环链表

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

代码如下

1
let current = queue.pending

2


3
while (true) {

4
  current = current.next

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

6
    break

7
  }

8
}

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

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

2
  current = current.next

3
}

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

原题地址：141. 环形链表

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

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1

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

2
输出：true

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

示例 2

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

2
输出：true

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

示例 3

1
输入：head = [1], pos = -1

2
输出：false

3
解释：链表中没有环。

解题思路：20250422
上一篇
2、链表
下一篇
4、栈
专栏首页
到顶
专栏目录