0160.相交链表

难度：🟢 简单

标签：哈希表、链表、双指针

链接：160. 相交链表

题目描述

给你两个单链表的头节点 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 （注意，如果两个链表相交则必须从相交节点开始往后完全相同）。
从各自的表头开始算起，链表 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'

示例 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 都大于 0，则输入链表必须为空。
两个链表不相交，因此返回 null 。

解题思路

核心思想

本题最巧妙的解法是利用 双指针 走过相同的路程，最终在相交点相遇。我们可以设想有两个人（指针 pA 和 pB）分别从两条链表的头节点 headA 和 headB 出发。当一个人走完自己的路（到达 null）时，就立刻切换到对方的起点继续走。

• pA 的路径：A 链 -> B 链

• pB 的路径：B 链 -> A 链

如果两个链表相交，设 A 的非相交部分长度为 a，B 的非相交部分长度为 b，相交部分长度为 c。那么：

• pA 走 a+c 到达相交点时，pB 走了 b+c。

• pA 切换到 headB 后，再走 b 步到达相交点，总路程为 a+c+b。

• pB 切换到 headA 后，再走 a 步到达相交点，总路程为 b+c+a。 因为总路程相同，所以它们必然会在相交点相遇。如果两链表不相交，他们会同时走完 A链+B链 的长度，最终同时变为 null 并在 null 处“相遇”。

思路选择

双指针法 是解决此问题的最优解，因为它空间复杂度为 O(1)，且代码非常简洁优雅。

关键步骤

1. 初始化：创建两个指针，pointA = headA 和 pointB = headB。

2. 循环遍历：当 pointA 和 pointB 不相等时，持续循环。 a. 移动 pointA：如果 pointA 不为 null，则 pointA = pointA.next；如果 pointA 为 null（走完了 A 链），则让它切换到 B 链的头部，即 pointA = headB。 b. 移动 pointB：如果 pointB 不为 null，则 pointB = pointB.next；如果 pointB 为 null（走完了 B 链），则让它切换到 A 链的头部，即 pointB = headA。

3. 返回结果：当循环结束时，pointA 和 pointB 相等，此时它们共同指向的节点就是相交节点。如果两链表不相交，它们会同时变为 null，此时返回 null 也符合题意。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 * this.val = val;
 * this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }

    let pointA = headA, pointB = headB;

    while (pointA !== pointB) {
        // 如果 pointA 到达末尾，则切换到 headB；否则，走一步
        pointA = pointA === null ? headB : pointA.next;
        // 如果 pointB 到达末尾，则切换到 headA；否则，走一步
        pointB = pointB === null ? headA : pointB.next;
    }

    // 返回相遇点，如果无交点，则此时 pointA 和 pointB 都为 null
    return pointA;
};

复杂度分析

• 时间复杂度：O(m + n) 其中 m 和 n 分别是两个链表的长度。在最坏的情况下（无交点），每个指针都需要遍历两个链表一次。

• 空间复杂度：O(1) 我们只使用了 pointA 和 pointB 两个额外指针，空间消耗是恒定的。

相关题目

• 0141.环形链表

• 0021.合并两个有序链表

总结

本题的双指针解法是一个非常精妙的设计，它通过让两个指针走过“对称”的路径 (A+B 和 B+A) 来消除长度差，从而保证它们如果能在非 null 处相遇，该点必然是第一个交点。这个思路值得深入理解和学习。