如何检测Lisp列表（基于cons单元）中的循环？求低空间复杂度方案

传统的Floyd龟兔、Brent这些循环检测算法只适用于单链表——每个节点只有一个后继。但Cons单元有car和cdr两个分支，本质是在处理有向图的循环检测，这就导致单链表算法直接失效。下面是一些无需O(n)空间的实用方案，以及Lisp系统实际的处理方式：

• 利用节点冗余位的原地标记（Lisp实现首选）
  很多Lisp系统会打内存布局的主意：Cons单元的地址一般是对齐的，低几位（比如2位）永远是0，完全可以拿来当标记位用。遍历的时候，每碰到一个Cons单元，就把它的car或cdr的低位置1，标记成“已访问”；要是后续再碰到一个已经标记过的节点，直接就能判定存在循环；遍历结束后，记得回溯把所有标记位改回去，别破坏原数据。这种方法空间复杂度是O(1)，但依赖语言对内存的控制，属于特定环境下的最优解。

• 递归深度限制+局部追踪（Lisp打印场景常用）
  Lisp打印时其实不需要严格检测所有循环，很多时候靠深度阈值就能搞定——比如Common Lisp里的*print-circle*参数：设定一个递归深度上限，超过这个深度就直接输出循环标记（比如#1#）；同时只记录当前深度路径里的节点标识（比如地址的哈希前缀），快速比对有没有重复。这种方法不是100%覆盖所有循环，但在实际打印场景里足够用，空间开销极低，不需要存全量节点。

• 优化版DFS路径追踪（通用低空间）
  不用把所有节点塞进哈希表，只追踪当前递归路径上的节点就行：走每个分支时，把当前节点加到路径栈里；访问新节点前，先检查它是不是在当前栈里（栈的大小就是当前递归深度，远小于总节点数n）；回溯的时候把节点从栈里删掉。这种方法空间复杂度是O(d)，d是图的最大递归深度，对于大多数Lisp数据结构来说，d比n小得多。

实际Lisp系统的处理逻辑 #

拿Common Lisp的*print-circle*机制举例：

• 开启后，第一次碰到节点时给它分配一个标签（比如#1=），再次碰到就输出#1#来表示循环引用
• 底层一般是标记位+局部哈希表结合，只存当前已经标记过的节点，不会占用O(n)的全局空间
• 要是碰到非循环的深层结构，会自动切回普通打印模式，避免做无用功。

通用多后继图的低空间思路 #

如果脱离Lisp的内存布局，通用场景可以这么搞：

• 迭代加深搜索（IDS）+ 路径标记：每次限制搜索深度，在当前深度内追踪路径，不用全局哈希表
• 时间戳原地标记：如果节点允许修改，用递增的时间戳标记访问时间，重复遇到相同时间戳就说明有循环，遍历完再恢复。

内容的提问来源于stack exchange，提问作者Prgrm.celeritas