LeetCode 142. Linked List Cycle II 题解

LeetCode 142. Linked List Cycle II 题解题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。 如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。示例 1输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0 输出返回索引为 0 的链表节点 解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1 输出返回 null 解释链表中没有环。解题思路方法双指针快慢指针思路使用两个指针slow和fast分别以不同的速度遍历链表slow指针每次移动一步fast指针每次移动两步如果链表中存在环fast指针最终会追上slow指针当slow和fast相遇时将其中一个指针重置到链表头部然后两个指针以相同的速度移动当它们再次相遇时相遇的节点就是环的入口复杂度分析时间复杂度O(n)其中 n 是链表的长度。两个指针最多移动 n 次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法双指针快慢指针# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def detectCycle(self, head: ListNode) - ListNode: if not head or not head.next: return None # 初始化快慢指针 slow head fast head # 寻找环中的相遇点 while fast and fast.next: slow slow.next fast fast.next.next # 如果相遇说明存在环 if slow fast: # 将其中一个指针重置到链表头部 slow head # 以相同的速度移动两个指针再次相遇的点就是环的入口 while slow ! fast: slow slow.next fast fast.next return slow # 如果没有环返回 None return None测试用例测试用例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点测试用例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点测试用例 3输入head [1], pos -1输出返回 null总结本题是链表的经典问题主要考察对链表操作和双指针技巧的理解和应用。通过使用快慢指针我们可以不仅检测链表中是否存在环还可以找到环的入口。双指针的核心思想是通过让快指针以两倍的速度移动当链表中存在环时快指针最终会追上慢指针。然后将其中一个指针重置到链表头部以相同的速度移动两个指针它们再次相遇的点就是环的入口。这种方法不仅适用于环形链表 II 问题还可以应用于许多其他链表相关的问题例如相交链表、链表中点查找等。掌握双指针技巧对于解决链表问题非常重要。