【数据结构与算法-Day 11】从循环链表到约瑟夫环，一文搞定链表的终极形态

Langchain系列文章目录

01-玩转LangChain：从模型调用到Prompt模板与输出解析的完整指南
02-玩转 LangChain Memory 模块：四种记忆类型详解及应用场景全覆盖
03-全面掌握 LangChain：从核心链条构建到动态任务分配的实战指南
04-玩转 LangChain：从文档加载到高效问答系统构建的全程实战
05-玩转 LangChain：深度评估问答系统的三种高效方法（示例生成、手动评估与LLM辅助评估）
06-从 0 到 1 掌握 LangChain Agents：自定义工具 + LLM 打造智能工作流！
07-【深度解析】从GPT-1到GPT-4：ChatGPT背后的核心原理全揭秘
08-【万字长文】MCP深度解析：打通AI与世界的“USB-C”，模型上下文协议原理、实践与未来

Python系列文章目录

PyTorch系列文章目录

机器学习系列文章目录

深度学习系列文章目录

Java系列文章目录

JavaScript系列文章目录

Python系列文章目录

Go语言系列文章目录

Docker系列文章目录

数据结构与算法系列文章目录

01-【数据结构与算法-Day 1】程序世界的基石：到底什么是数据结构与算法？
02-【数据结构与算法-Day 2】衡量代码的标尺：时间复杂度与大O表示法入门
03-【数据结构与算法-Day 3】揭秘算法效率的真相：全面解析O(n^2), O(2^n)及最好/最坏/平均复杂度
04-【数据结构与算法-Day 4】从O(1)到O(n²)，全面掌握空间复杂度分析
05-【数据结构与算法-Day 5】实战演练：轻松看懂代码的时间与空间复杂度
06-【数据结构与算法-Day 6】最朴素的容器 - 数组（Array）深度解析
07-【数据结构与算法-Day 7】告别数组束缚，初识灵活的链表 (Linked List)
08-【数据结构与算法-Day 8】手把手带你拿捏单向链表：增、删、改核心操作详解
09-【数据结构与算法-Day 9】图解单向链表：从基础遍历到面试必考的链表反转
10-【数据结构与算法-Day 10】双向奔赴：深入解析双向链表（含图解与代码）
11-【数据结构与算法-Day 11】从循环链表到约瑟夫环，一文搞定链表的终极形态

---

文章目录

• Langchain系列文章目录
• Python系列文章目录
• PyTorch系列文章目录
• 机器学习系列文章目录
• 深度学习系列文章目录
• Java系列文章目录
• JavaScript系列文章目录
• Python系列文章目录
• Go语言系列文章目录
• Docker系列文章目录
• 数据结构与算法系列文章目录
• 摘要
• 一、什么是循环链表？
• • 1.1 从单向链表到循环链表
  • 1.2 循环链表的定义与结构
  • • 1.2.1 结构定义
    • 1.2.2 可视化表示
    • 1.2.3 与普通链表的区别
• 二、循环链表的核心操作与判断
• • 2.1 创建与遍历
  • • • （1） 创建一个循环链表
      • （2） 遍历循环链表
  • 2.2 如何判断一个链表是否带环？
  • • 2.2.1 问题描述
    • 2.2.2 快慢指针法（Floyd 判环算法）
    • 2.2.3 代码实现
• 三、经典应用：约瑟夫问题 (Josephus Problem)
• • 3.1 问题背景：生死游戏
  • 3.2 为什么用循环链表？
  • 3.3 解题思路分析
  • • 3.3.1 步骤一：构建循环链表
    • 3.3.2 步骤二：模拟报数与删除
    • 3.3.3 步骤三：找到最后的幸存者
  • 3.4 代码实现与详解
• 四、终极对决：数组 vs. 链表
• • 4.1 存储结构
  • 4.2 核心操作效率对比
  • 4.3 空间开销
  • 4.4 场景选择指南
• 五、总结

---

摘要

本文是数据结构与算法系列的第十一篇，将带领读者进入一个“首尾相连”的奇妙世界——循环链表。我们将从循环链表的基本概念和结构出发，深入探讨其与普通链表的异同，并详细讲解如何通过“快慢指针法”判断链表是否带环。本文的核心将聚焦于一个经典的算法问题——约瑟夫问题，并通过循环链表给出清晰的解题思路与完整的代码实现。最后，我们将对数组和链表这两大基础线性结构进行一次全方位的终极对比，帮助你彻底理解它们的优劣势与适用场景，为未来的技术选型打下坚实基础。

一、什么是循环链表？

在之前的文章中，我们已经熟悉了单向链表和双向链表。它们就像一条条铁链，每个节点环环相扣。但它们都有一个共同的特点：链条有明确的起点（头节点）和终点（尾节点的 next 指针为 null）。这就像一条单行道，走到了尽头就是终点。但如果我们将这条路的尽头和起点连接起来，形成一个闭环，会发生什么呢？这就是循环链表的思想。

1.1 从单向链表到循环链表

想象一下，一个普通的单向链表，它的最后一个节点的 next 指针指向 null，表示链表的结束。这在逻辑上是清晰的，但也意味着一旦我们到达了尾部，就无法再方便地回到链表的头部，除非我们重新从头节点开始遍历。

循环链表（Circular Linked List）正是为了改变这一“断开”的状态。它对传统链表做了一个小小的改动，却带来了全新的特性：将尾节点的 next 指针不再指向 null，而是指向头节点。

1.2 循环链表的定义与结构

1.2.1 结构定义

循环链表是一种特殊的链式存储结构。在单向循环链表中，最后一个节点的指针域指向头节点，而不是像普通单向链表那样指向空（null）。这使得整个链表形成一个环，从任何一个节点出发，只要不断地沿着 next 指针移动，最终都能回到起点。

1.2.2 可视化表示

一个简单的单向循环链表结构可以用下图表示，节点 4 的 next 指针指向了头节点 1，形成了一个闭环。

#mermaid-svg-3DRXQNYaMXuHBRph {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3DRXQNYaMXuHBRph .error-icon{fill:#552222;}#mermaid-svg-3DRXQNYaMXuHBRph .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-3DRXQNYaMXuHBRph .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-3DRXQNYaMXuHBRph .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-3DRXQNYaMXuHBRph .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-3DRXQNYaMXuHBRph .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-3DRXQNYaMXuHBRph .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-3DRXQNYaMXuHBRph .marker{fill:#333333;stroke:#333333;}#mermaid-svg-3DRXQNYaMXuHBRph .marker.cross{stroke:#333333;}#mermaid-svg-3DRXQNYaMXuHBRph svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-3DRXQNYaMXuHBRph .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-3DRXQNYaMXuHBRph .cluster-label text{fill:#333;}#mermaid-svg-3DRXQNYaMXuHBRph .cluster-label span{color:#333;}#mermaid-svg-3DRXQNYaMXuHBRph .label text,#mermaid-svg-3DRXQNYaMXuHBRph span{fill:#333;color:#333;}#mermaid-svg-3DRXQNYaMXuHBRph .node rect,#mermaid-svg-3DRXQNYaMXuHBRph .node circle,#mermaid-svg-3DRXQNYaMXuHBRph .node ellipse,#mermaid-svg-3DRXQNYaMXuHBRph .node polygon,#mermaid-svg-3DRXQNYaMXuHBRph .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-3DRXQNYaMXuHBRph .node .label{text-align:center;}#mermaid-svg-3DRXQNYaMXuHBRph .node.clickable{cursor:pointer;}#mermaid-svg-3DRXQNYaMXuHBRph .arrowheadPath{fill:#333333;}#mermaid-svg-3DRXQNYaMXuHBRph .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-3DRXQNYaMXuHBRph .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-3DRXQNYaMXuHBRph .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-3DRXQNYaMXuHBRph .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-3DRXQNYaMXuHBRph .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-3DRXQNYaMXuHBRph .cluster text{fill:#333;}#mermaid-svg-3DRXQNYaMXuHBRph .cluster span{color:#333;}#mermaid-svg-3DRXQNYaMXuHBRph div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-3DRXQNYaMXuHBRph :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;} 单向循环链表 Node 2 Node 1 Node 3 Node 4

1.2.3 与普通链表的区别

循环链表和普通链表最核心的区别在于两点：

1. 尾指针的指向：普通链表的尾节点指向 null；循环链表的尾节点指向头节点。
2. 遍历的终止条件：遍历普通链表时，我们以 currentNode == null 作为循环结束的标志。而在遍历循环链表时，由于永远不会遇到 null，我们的终止条件通常是 currentNode.next == head（当我们再次到达头节点的前一个节点时）或类似的判断。从头节点开始遍历，当再次遇到头节点时，表示已经遍历了一整圈。

二、循环链表的核心操作与判断

循环链表的增删改查操作与普通链表类似，主要区别在于处理边界条件，尤其是涉及到头尾节点的操作时，需要同时维护环的结构。但在这里，我们探讨一个更有趣且常见的问题：如何判断一个链表是否“带环”？

2.1 创建与遍历

（1） 创建一个循环链表

创建一个循环链表很简单，只需在创建完所有节点并连接后，找到尾节点，让它的 next 指向头节点即可。

// Java 节点定义class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; }}// 创建一个简单的循环链表 1 -> 2 -> 3 -> 1ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);// 找到尾节点ListNode tail = head.next.next;// 将尾节点的 next 指向头节点，形成环tail.next = head;

（2） 遍历循环链表

遍历循环链表时要格外小心，因为简单的 while(current != null) 会导致无限循环。正确的做法是，从头节点开始，当再次回到头节点时停止。

public void printCircularLinkedList(ListNode head) { if (head == null) { return; } ListNode current = head; System.out.print(\"链表内容: \"); do { System.out.print(current.val + \" -> \"); current = current.next; } while (current != head); // 关键：当 current 再次等于 head 时，说明已经遍历了一圈 System.out.println(\" (回到起点)\");}

注意：这里使用 do-while 循环非常巧妙。因为它会先执行一次循环体再判断条件，确保了即使链表只有一个节点（自己指向自己），也能正确打印并退出。

2.2 如何判断一个链表是否带环？

这是一个非常经典的面试题。一个“带环”的链表不一定是一个完美的循环链表（尾连头），它的环可能出现在链表的中间部分。

2.2.1 问题描述

给定一个链表的头节点 head，判断该链表中是否有环。如果链表中存在环，则返回 true。否则，返回 false。

2.2.2 快慢指针法（Floyd 判环算法）

解决这个问题的最优方法是快慢指针法，也称为“龟兔赛跑”算法。

核心思想：

1. 设置两个指针 slow 和 fast，初始时都指向头节点 head。
2. slow 指针每次向前移动一步。
3. fast 指针每次向前移动两步。
4. 如果链表中存在环，那么 fast 指针（兔子）最终一定会追上并与 slow 指针（乌龟）相遇。
5. 如果 fast 指针或 fast.next 指针到达了链表的末端（即为 null），则说明链表中没有环。

2.2.3 代码实现

public class Solution { public boolean hasCycle(ListNode head) { // 如果链表为空或只有一个节点，不可能有环 if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; // fast 从 head.next 开始，或都从head开始，循环内先移动再判断 while (slow != fast) { // fast 指针走到头了，说明没有环 if (fast == null || fast.next == null) { return false; } // slow 走一步 slow = slow.next; // fast 走两步 fast = fast.next.next; } // 如果循环结束，说明 slow 和 fast 相遇了 return true; }}

三、经典应用：约瑟夫问题 (Josephus Problem)

约瑟夫问题是一个经典的基于循环链表（或循环数组）的问题，它完美地展示了循环结构的用武之地。

3.1 问题背景：生死游戏

据说在古代，犹太历史学家约瑟夫斯和他的 39 个同伴被罗马军队包围。他们宁死不屈，决定集体自杀。他们站成一个圈，从某个人开始报数，每报到 3 的人就被处决。然后从下一个人重新开始报数，直到剩下最后一个人，这个人可以幸免。约瑟夫斯迅速计算出了幸存者的位置，并最终活了下来。

问题的抽象描述：
N 个人围成一圈，从第一个人开始按顺序报数（从 1 到 M）。每报到 M 的那个人出列，他的下一个人又从 1 开始报数，如此循环，直到所有人出列。求出列的顺序。

3.2 为什么用循环链表？

这个问题天然就具备“环”的特性：

• N 个人围成一圈：这不正是一个循环链表吗？每个人是一个节点。
• 从下一个人继续：当一个人出列后，链表需要“断开”并“重连”，循环的结构保持不变。

使用循环链表来模拟这个过程，逻辑会非常直观和清晰。

3.3 解题思路分析

3.3.1 步骤一：构建循环链表

首先，我们需要创建一个包含 N 个节点的循环链表，来代表 N 个人。每个节点可以存储人的编号（例如 1 到 N）。

3.3.2 步骤二：模拟报数与删除

报数的过程就是链表指针移动的过程。要找到第 M 个人，我们只需要从当前节点开始，向后移动 M-1 步。

关键点：要删除一个节点，我们必须找到它的前驱节点。因此，移动 M-1 步后，我们实际上是停在了待删除节点的前一个位置。然后执行删除操作：prev.next = prev.next.next。

3.3.3 步骤三：找到最后的幸存者

整个过程在一个大循环中进行，直到链表中只剩下一个节点。每次循环都淘汰一个人。

3.4 代码实现与详解

import java.util.ArrayList;import java.util.List;public class JosephusProblem { // 内部节点类 static class Node { int id; Node next; Node(int id) { this.id = id; } } public static List<Integer> solve(int n, int m) { if (n <= 0 || m <= 0) { return new ArrayList<>(); } List<Integer> outSequence = new ArrayList<>(); // 1. 构建循环链表 Node head = new Node(1); Node current = head; for (int i = 2; i <= n; i++) { current.next = new Node(i); current = current.next; } current.next = head; // 尾节点指向头节点，形成环 // 2. 模拟报数与删除 Node prev = current; // prev 始终是 current 的前驱节点 current = head; while (current.next != current) { // 当链中不止一个节点时 // 移动 m-1 步，找到要删除节点的前驱 for (int i = 1; i < m; i++) { prev = current; current = current.next; } // 此时 current 指向要被删除的节点 outSequence.add(current.id); System.out.println(\"出列: \" + current.id); // 删除 current 节点 prev.next = current.next; // 从下一个节点继续开始 current = prev.next; } // 3. 添加最后一个幸存者 outSequence.add(current.id); System.out.println(\"幸存者: \" + current.id); return outSequence; } public static void main(String[] args) { // 5 个人，报数为 2 的出列 solve(5, 2); }}

四、终极对决：数组 vs. 链表

学到这里，我们已经掌握了最主要的两种线性数据结构：数组和链表（包括其变种）。是时候对它们进行一次全面的对比总结了。

4.1 存储结构

• 数组 (Array): 存储在一块连续的内存空间中。像电影院的连排座位，每个座位都有明确的编号。
• 链表 (Linked List): 存储在离散的、非连续的内存空间中。像寻宝游戏，每个宝箱（节点）里除了宝物（数据），还有一张指向下一个宝箱位置的地图（指针）。

4.2 核心操作效率对比

操作 数组 (Array) 链表 (Linked List) 性能分析 随机访问 (按索引读写) $O(1)$ $O(n)$ 数组通过 base_address + index * size 公式可立即定位，链表必须从头遍历。 查找元素 (按值) $O(n)$ $O(n)$ 无论哪种结构，在最坏情况下都需要遍历所有元素。 插入/删除 (头部) $O(n)$ $O(1)$ 数组头部插入/删除需要移动后面所有元素，链表只需改变头指针。 插入/删除 (尾部) $O(1)$* $O(1)$** *数组若不考虑扩容，是 $O(1)$。**链表若有尾指针，是 $O(1)$；单向链表无尾指针则是 $O(n)$。 插入/删除 (中间) $O(n)$ $O(n)$ 数组需要移动元素 ($O(n)$)。链表虽然插入/删除本身是 $O(1)$，但找到那个位置需要 $O(n)$。

4.3 空间开销

• 数组: 存在空间浪费问题。你必须在创建时声明一个固定大小，如果用不完，多余的空间就被浪费了。如果空间不够，就需要扩容，这是一个成本较高的操作。
• 链表: 空间利用率更高，按需分配。每创建一个节点就分配一块内存。但其缺点是每个节点都需要额外的空间来存储指针，当数据本身很小时，指针的开销占比会很明显。

4.4 场景选择指南

选择数组 (Array) 的场景 选择链表 (Linked List) 的场景 1. 数据量在创建时已知或基本固定。 1. 数据量无法预估，需要动态增删。 2. 需要频繁地通过索引进行随机访问和查找。 2. 需要频繁地在表头或表尾进行插入和删除操作。 3. 对内存要求苛刻，希望消除指针带来的额外开销。 3. 对随机访问性能要求不高。 4. 逻辑简单，易于理解和实现。 4. 内存不要求连续，可以有效利用碎片化的内存。

一句话总结：频繁访问选数组，频繁增删选链表。

五、总结

本文我们深入探索了链表家族的一位特殊成员——循环链表，并用它解决了经典的约瑟夫问题。这不仅是对链表知识的深化，更是算法思维在具体问题中应用的体现。

1. 循环链表的核心：循环链表的本质是将普通链表的“终点”与“起点”相连，形成一个闭环。这使得遍历可以无限进行，也改变了操作的边界条件。
2. 判断链表带环：快慢指针（Floyd判环算法）是判断链表是否有环的高效标准解法，其“龟兔赛跑”的思想在很多问题中都有应用。
3. 约瑟夫问题的启示：约瑟夫问题展示了如何将一个现实问题抽象成数据结构模型，并利用该结构的特性来优雅地解决问题。循环链表是该问题的天然模拟器。
4. 数组与链表的权衡：没有完美的数据结构，只有最适合场景的数据结构。理解数组（随机访问快）和链表（增删灵活）的根本差异，是成为一名优秀程序员的基础内功。选择哪一个，取决于你最看重的是什么操作的效率。

---