LeetCode 热题 100 160. 相交链表

LeetCode 热题 100 | 160. 相交链表

大家好，今天我们来解决一道经典的算法题——相交链表。这道题在LeetCode上被标记为简单难度，要求我们找到两个单链表相交的起始节点。如果两个链表没有相交，则返回 null。下面我将详细讲解解题思路，并附上Python代码实现。

问题描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

注意：

• 题目数据保证整个链式结构中不存在环。
• 函数返回结果后，链表必须保持其原始结构。

示例：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：
链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解题思路

核心思想

1. 双指针法：

   • 使用两个指针 pA 和 pB，分别从 headA 和 headB 开始遍历链表。
   • 当 pA 到达链表末尾时，将其重定向到 headB；当 pB 到达链表末尾时，将其重定向到 headA。
   • 如果两个链表相交，pA 和 pB 会在相交节点相遇；如果不相交，pA 和 pB 会同时到达链表末尾（null）。

2. 数学原理：

   • 设链表 A 的长度为 m，链表 B 的长度为 n，相交部分长度为 c。
   • 如果两个链表相交，pA 和 pB 分别遍历 m + n - c 步后会相遇。

Python代码实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None
    
    pA, pB = headA, headB
    
    # 遍历链表，直到两个指针相遇或同时到达末尾
    while pA != pB:
        # 如果 pA 到达末尾，重定向到 headB
        pA = pA.next if pA else headB
        # 如果 pB 到达末尾，重定向到 headA
        pB = pB.next if pB else headA
    
    # 返回相遇节点（如果相交）或 None（如果不相交）
    return pA

代码解析

1. 初始化指针：

   • pA 和 pB 分别指向 headA 和 headB。

2. 遍历链表：

   • 当 pA 和 pB 不相等时，继续遍历。
   • 如果 pA 到达链表末尾，将其重定向到 headB。
   • 如果 pB 到达链表末尾，将其重定向到 headA。

3. 返回结果：

   • 如果两个链表相交，pA 和 pB 会在相交节点相遇。
   • 如果两个链表不相交，pA 和 pB 会同时到达链表末尾（null）。

复杂度分析

• 时间复杂度：O(m + n)，其中 m 和 n 分别是链表 A 和链表 B 的长度。两个指针最多遍历 m + n 个节点。
• 空间复杂度：O(1)，只使用了常数个额外空间。

示例运行

示例1

输入：
intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：
链表 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'
解释：
链表 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
输出：No intersection
解释：
链表 A 为 [2,6,4]，链表 B 为 [1,5]。
这两个链表不相交，因此返回 null。

总结

通过双指针法，我们可以高效地找到两个链表的相交节点。这种方法不仅简洁，而且效率非常高，适合处理类似的问题。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！