LeetCode 141. Linked List Cycle 题解

LeetCode 141. Linked List Cycle 题解题目描述给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。示例 1输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。解题思路方法一哈希表遍历链表将每个节点存储到哈希表中如果遇到重复的节点说明存在环方法二快慢指针快指针每次移动两步慢指针每次移动一步如果存在环快指针会追上慢指针代码实现方法一哈希表class ListNode: def __init__(self, x): self.val x self.next None def hasCycle(head): seen set() current head while current: if current in seen: return True seen.add(current) current current.next return False方法二快慢指针def hasCycle(head): if not head or not head.next: return False slow head fast head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True复杂度分析方法时间复杂度空间复杂度哈希表O(n)O(n)快慢指针O(n)O(1)测试案例# 测试案例 1 # 创建有环的链表 head ListNode(3) node2 ListNode(2) node0 ListNode(0) node4 ListNode(-4) head.next node2 node2.next node0 node0.next node4 node4.next node2 # 形成环 assert hasCycle(head) True # 测试案例 2 head ListNode(1) head.next ListNode(2) head.next.next head # 形成环 assert hasCycle(head) True # 测试案例 3 head ListNode(1) assert hasCycle(head) False总结本题是链表环检测的经典问题。关键点哈希表记录访问过的节点快慢指针龟兔赛跑算法时间和空间复杂度的权衡通过本题可以深入理解链表操作和环检测算法。