检查链表有环

检查链表是否有环,貌似目前的标准答案是使用两根指针。下面是Emacs中的实现,亮点在指针变量命名。

/* Signal `error' with message S, and additional arg ARG.
   If ARG is not a genuine list, make it a one-element list.  */

void
signal_error (const char *s, Lisp_Object arg)
{
  Lisp_Object tortoise, hare;

  hare = tortoise = arg;
  while (CONSP (hare))
    {
      hare = XCDR (hare);
      if (!CONSP (hare))
	break;

      hare = XCDR (hare);
      tortoise = XCDR (tortoise);

      if (EQ (hare, tortoise))
	break;
    }

  if (!NILP (hare))
    arg = Fcons (arg, Qnil);	/* Make it a list.  */

  xsignal (Qerror, Fcons (build_string (s), arg));
}

在Emacs源码中搜索tortoise,可以发现多处类似实现。

One thought on “检查链表有环

  1. wei jin says:

    这好像是著名的面试题, 有个不太靠谱的答案 就是 比如小链表 那就让它转10秒钟之类的,要是能停下 就没环, 停不下有环

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据