IT 面试题库

如何判断链表是否有环?

中级编程题算法工程师Java开发工程师硬件工程师芯片设计工程师(IC设计)链表快慢指针算法

题目

给出快慢指针(Floyd)解法与原理。

参考答案

内容深度:适中 · 含示例/代码 · 来源:种子题库 · 未复核 · 89 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

Floyd 快慢指针:慢指针一次走 1 步,快指针一次走 2 步。若有环,二者必在环内相遇;若无环,快指针先到 null。

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast: return True
    return False

相遇原理:入环后快指针相对慢指针每步追 1,差距逐步缩小必追上。时间 O(n)、空间 O(1)。

进阶:相遇点再从头与慢指针同步走,交点即环入口(数学可证)。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题