【算法题】如何判断一个单向链表是否有环?
如何判断一个单向链表是否含有环,是 LintCode 第 102 题,也是企业面试中的高频考点。文章先分析有环链表的形态:它有头结点却没有尾结点,内部包含一个把尾结点指回头结点的环状结构,因此遍历永远不会自然停止。由此引出最关键的一个洞察——在环状链表中若让两个指针以不同速度遍历,必然会出现类似田径比赛里的套圈现象,而这正是普通单向链表绝不会具备的特征。解法即经典的快慢指针:fast 每次前进两步、slow 每次前进一步,若任一指针先到达链表尾部则证明无环,若两者在某个位置重新相遇则说明链表有环。文中配有结构示意图和完整的 Java 参考实现。