LeetCode链表之如何查找两个链表的第一个公共节点

在LeetCode的链表问题中，查找两个链表的第一个公共节点是一个经典且常见的问题。这类问题不仅考察了对链表结构的理解，还涉及到了双指针技巧的应用。本文将详细介绍如何解决这个问题，并通过代码示例和图示帮助读者更好地理解。

问题描述

给定两个单链表，编写一个函数来找到它们的第一个公共节点。如果两个链表没有公共节点，则返回 null。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
解释：第一个公共节点的值为 8（注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
解释：第一个公共节点的值为 2（注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,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。

解题思路

要解决这个问题，我们需要找到两个链表的第一个公共节点。公共节点是指两个链表从某个节点开始，后续的节点完全相同。我们可以通过以下几种方法来解决这个问题：

方法一：哈希表法

我们可以使用哈希表来存储其中一个链表的所有节点，然后遍历另一个链表，检查每个节点是否在哈希表中。如果存在，则该节点就是第一个公共节点。

步骤：

1. 遍历链表A，将每个节点存入哈希表中。
2. 遍历链表B，检查每个节点是否在哈希表中。
3. 如果找到第一个在哈希表中的节点，则返回该节点。
4. 如果遍历完链表B仍未找到公共节点，则返回 null。

代码实现：

def getIntersectionNode(headA, headB):
    nodes = set()
    while headA:
        nodes.add(headA)
        headA = headA.next
    while headB:
        if headB in nodes:
            return headB
        headB = headB.next
    return None

时间复杂度： O(m + n)，其中 m 和 n 分别是链表A和链表B的长度。

空间复杂度： O(m)，因为我们需要存储链表A的所有节点。

方法二：双指针法

双指针法是一种更高效的方法，它不需要额外的空间。我们可以通过调整两个指针的遍历路径，使得它们在第一个公共节点相遇。

步骤：

1. 初始化两个指针 pA 和 pB，分别指向链表A和链表B的头节点。
2. 同时遍历两个链表，pA 和 pB 每次向后移动一个节点。
3. 如果 pA 到达链表A的末尾，则将其指向链表B的头节点；如果 pB 到达链表B的末尾，则将其指向链表A的头节点。
4. 当 pA 和 pB 相遇时，即为第一个公共节点。

代码实现：

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

时间复杂度： O(m + n)，其中 m 和 n 分别是链表A和链表B的长度。

空间复杂度： O(1)，只使用了常数级别的额外空间。

方法三：长度差法

我们可以先计算两个链表的长度差，然后让较长的链表的指针先移动长度差的步数，使得两个链表的剩余长度相同。然后同时遍历两个链表，找到第一个相同的节点。

步骤：

1. 计算链表A和链表B的长度 lenA 和 lenB。
2. 计算长度差 diff = abs(lenA - lenB)。
3. 让较长的链表的指针先移动 diff 步。
4. 同时遍历两个链表，找到第一个相同的节点。

代码实现：

def getIntersectionNode(headA, headB):
    def getLength(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length
    
    lenA, lenB = getLength(headA), getLength(headB)
    pA, pB = headA, headB
    if lenA > lenB:
        for _ in range(lenA - lenB):
            pA = pA.next
    else:
        for _ in range(lenB - lenA):
            pB = pB.next
    while pA != pB:
        pA = pA.next
        pB = pB.next
    return pA

时间复杂度： O(m + n)，其中 m 和 n 分别是链表A和链表B的长度。

空间复杂度： O(1)，只使用了常数级别的额外空间。

总结

在LeetCode的链表问题中，查找两个链表的第一个公共节点是一个常见的问题。我们可以通过哈希表法、双指针法和长度差法来解决这个问题。其中，双指针法是最优的解决方案，因为它不需要额外的空间，并且时间复杂度为 O(m + n)。

在实际应用中，我们可以根据具体的需求选择合适的解决方案。如果空间复杂度不是问题，哈希表法是一个简单直观的选择；如果追求最优的空间复杂度，双指针法是最佳选择。

希望本文能够帮助读者更好地理解如何查找两个链表的第一个公共节点，并在LeetCode的链表问题中取得更好的成绩。