LeetCode 160. Intersection of Two Linked Lists 题解

LeetCode 160. Intersection of Two Linked Lists 题解题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回null。示例 1输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at 8 解释相交节点的值为 8 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,6,1,8,4,5]。 在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。示例 2输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1 输出Intersected at 2 解释相交节点的值为 2 注意如果两个链表相交则不能为 0。 从各自的表头开始算起链表 A 为 [1,9,1,2,4]链表 B 为 [3,2,4]。 在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2 输出null 解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。 由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。 这两个链表不相交因此返回 null。解题思路方法一哈希表思路使用哈希表来存储链表 A 的所有节点遍历链表 B检查每个节点是否在哈希表中如果找到则返回该节点否则返回null复杂度分析时间复杂度O(m n)其中 m 和 n 分别是两个链表的长度。需要遍历两个链表各一次。空间复杂度O(m)其中 m 是链表 A 的长度。需要使用哈希表来存储链表 A 的所有节点。方法二双指针思路使用两个指针pA和pB分别指向两个链表的头节点同时移动两个指针当一个指针到达链表末尾时将其指向另一个链表的头节点继续移动指针当两个指针相遇时返回相遇的节点如果两个链表不相交最终两个指针都会指向null复杂度分析时间复杂度O(m n)其中 m 和 n 分别是两个链表的长度。两个指针最多移动 m n 次。空间复杂度O(1)只需要常数级的额外空间。代码实现方法一哈希表# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: # 使用哈希表存储链表 A 的所有节点 nodes set() p headA while p: nodes.add(p) p p.next # 遍历链表 B检查每个节点是否在哈希表中 p headB while p: if p in nodes: return p p p.next return None方法二双指针# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val x # self.next None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: pA headA pB headB while pA ! pB: # 如果 pA 到达链表末尾将其指向链表 B 的头节点 pA pA.next if pA else headB # 如果 pB 到达链表末尾将其指向链表 A 的头节点 pB pB.next if pB else headA return pA测试用例测试用例 1输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3输出Intersected at 8测试用例 2输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1输出Intersected at 2测试用例 3输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2输出null总结本题是链表的经典问题主要考察对链表操作和双指针技巧的理解和应用。通过使用哈希表或双指针我们可以高效地找到两个链表的相交节点。哈希表的核心思想是存储一个链表的所有节点然后遍历另一个链表检查每个节点是否在哈希表中。双指针的核心思想是通过让两个指针分别遍历两个链表当一个指针到达末尾时切换到另一个链表的头部最终两个指针会在相交节点相遇。在实际应用中双指针方法通常更受欢迎因为它的空间复杂度更低只需要常数级的额外空间。这种方法不仅适用于相交链表问题还可以应用于许多其他链表相关的问题例如环形链表检测、链表中点查找等。掌握双指针技巧对于解决链表问题非常重要。