从链表存在环的问题说起

有这样一个经典的算法题,说是一个单向链表,它内部可能存在环,也可能不存在,用怎样的方法,可以检测出,这个链表是否存在环。下图即是这个形成环的示意,如果单向链表的尾部,指向了链表中的一个节点,而不是指向空,那就构成环了。

接着的一个问题是,怎么检测出这个链表是否有环?

看到这个问题,也许你会觉得,太简单了,但是这个问题只是一个引子。在 《求第 K 个数的问题》一文中,我从简入深,逐步展开,把这 “第 K 个数” 的一系列问题翻了个底朝天。我想关于这个链表成环问题,我也利用类似的思路,看看我是不是也能把这一个问题前前后后讲清楚。

判断单向链表是否成环

在进一步思考

[……]阅读全文
back to top