题目链接

链表相交

题目描述

给定两个无环的单链表，它们可能在某一节点开始相交。请实现函数 getIntersectionNode，计算并返回两个链表的第一个交点节点。如果不存在交点，则返回 null。

注意:

  • 交点是指节点引用（内存地址）相同，而不仅仅是节点值相同。
  • 这是一个主函数模式的题目，你只需要补充 getIntersectionNode 函数的内部代码即可。

示例: 输入: headA = [4,1,8,4,5], headB = [5,0,1,8,4,5] （其中链表A的8和链表B的8是同一个节点）

输出: 值为 8 的节点。

解题思路

寻找两个链表的交点是一个经典问题。关键在于如何消除两个链表在到达交点前的"长度差"。

方法一：计算长度差

这是一个非常直观的方法。如果两个链表相交，那么从交点到链表末尾的部分是完全共享的。这意味着，如果我们能让两个指针在距离链表末尾相同长度的地方开始同步前进，它们必然会在交点相遇。

算法步骤:

  1. 计算长度: 分别遍历两个链表 headA 和 headB，得到它们的长度 lenA 和 lenB。
  2. 计算差值: 计算长度差 diff = abs(lenA - lenB)。
  3. 对齐指针:
    • 让指向较长链表的指针先前进 diff 步。
    • 例如，如果 lenA > lenB，则让指针 pA 从 headA 开始先走 diff 步。
  4. 同步前进: 现在，两个指针 pA 和 pB 距离各自的链表末尾有相同的步数。我们让它们同步向后移动，一次一步。
  5. 寻找交点:
    • 它们相遇的第一个节点 (pA == pB) 就是第一个公共节点。
    • 如果它们一直走到末尾（都变为 null）都没有相遇，说明链表不相交。

方法二：巧妙的双指针法 (推荐)

这是一个非常优雅的解法，它避免了显式地计算长度。

核心思想: 让两个指针 pA 和 pB 分别从 headA 和 headB 出发。当任意一个指针走到自己链表的末尾时，就将它重定向到另一个链表的头部，然后继续前进。

为什么这个方法可行？

  • 如果两链表相交: 假设链表A在交点前的长度为 a，链表B在交点前的长度为 b，公共部分的长度为 c。

    • 指针 pA 走过的路径长度为 a + c (到达末尾) + b (从B的头走到交点)。总路程 a+c+b。
    • 指针 pB 走过的路径长度为 b + c (到达末尾) + a (从A的头走到交点)。总路程 b+c+a。 因为总路程相同，所以两个指针必然会在交点相遇。

  • 如果两链表不相交:

    • 指针 pA 走过的路径长度为 lenA + lenB。
    • 指针 pB 走过的路径长度为 lenB + lenA。 它们走完相同的路程后，会同时到达终点（都变为 null）。此时 pA == pB (null == null)，循环终止，返回 null，正确。

算法步骤:

  1. 初始化两个指针 pA = headA 和 pB = headB。
  2. 进入一个循环，当 pA != pB 时继续： a. 移动 pA：如果 pA 不为 null，则 pA = pA.next；否则，pA = headB。 b. 移动 pB：如果 pB 不为 null，则 pB = pB.next；否则，pB = headA。
  3. 循环结束后，pA (或 pB) 就是交点或 null。

代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr) {
        return nullptr;
    }
    ListNode *pA = headA, *pB = headB;
    // 当pA和pB相遇时，循环终止
    while (pA != pB) {
        // pA走完链表A，就去走链表B
        pA = (pA == nullptr) ? headB : pA->next;
        // pB走完链表B，就去走链表A
        pB = (pB == nullptr) ? headA : pB->next;
    }
    return pA; // 返回交点或null
}

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pA = headA, pB = headB;
    // 当pA和pB相遇时，循环终止
    while (pA != pB) {
        // pA走完链表A，就去走链表B
        pA = (pA == null) ? headB : pA.next;
        // pB走完链表B，就去走链表A
        pB = (pB == null) ? headA : pB.next;
    }
    return pA; // 返回交点或null
}

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None
    
    pA, pB = headA, headB
    
    # 当pA和pB相遇时，循环终止
    while pA is not pB:
        # pA走完链表A，就去走链表B
        pA = headB if pA is None else pA.next
        # pB走完链表B，就去走链表A
        pB = headA if pB is None else pB.next
        
    return pA # 返回交点或None

算法及复杂度

  • 算法: 双指针法
  • 时间复杂度: ，其中 和 分别为两个链表的长度。在最坏情况下（无交点或交点在末尾），每个指针都需要遍历两个链表一次。
  • 空间复杂度: 。我们只使用了常数个额外指针。