循环链表 · 考级冲刺

把尾节点的 next 指回头节点，链表就首尾相连成一个圈，这就是循环链表。它没有真正的「结尾 nullptr」，顺着走会一圈圈转下去，特别适合「转圈报数」这类问题。

// 用数组模拟一个 n 人的循环链表
for (int i = 1; i <= n; i++)
    nxt[i] = (i == n) ? 1 : i + 1;   // 尾指回头，成环

怎么判断「走完一圈」？不能再靠 nullptr 了。常用办法：（1）记住出发节点，再回到它就是一圈；（2）计步数，走满 $n$ 步即一圈；（3）配合规模，删到只剩一个节点为止（约瑟夫问题）。

复杂度：遍历一圈仍是 $O (n)$ 。

考试常见坑：（1）遍历循环链表若还写 while (p != nullptr) 会死循环，必须换成「回到起点」或「计数」作为终止条件；（2）建环时别忘把最后一个的 next 接回头，漏了就退化成普通单链表；（3）删到最后一个节点时，它的 next 指向自己，要特判避免死循环。