相交链表 - Stellar Observer Protocol

533 字

3 分钟

相交链表

2025-08-19

Algorithms

哈希表

/

双指针

/

链表

题目描述#

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

解题思路#

双指针路径补偿法：
- 初始化两个指针分别指向两个链表头节点
- 指针同步遍历链表，到达尾部时跳转至另一链表头部
相遇点即交点：
- 若链表相交，两指针会在交点相遇
- 若不相交，两指针最终同时到达尾部（null）
路径长度分析：
- 每个指针都遍历”链表A非公共部分 + 链表B非公共部分 + 公共部分”
- 路径长度相等确保必然相遇
边界处理：
- 处理空链表输入
- 处理无交点情况

关键洞察#

路径补偿原理：
- 交换遍历路径消除长度差
- 保证两指针同时遍历总长度L1+L2
交点特性：
- 相交点后序列完全一致
- 相遇点即为首个公共节点
终止条件：
- 指针相遇或同时为null终止
效率优化：
- 无需计算链表长度
- 无需额外存储空间

复杂度分析#

指标	说明
时间复杂度	O(m+n)：最多遍历两个链表各一次
空间复杂度	O(1)：仅使用两个指针

代码实现#

1
/**
2
 * @link {https://leetcode.cn/problems/intersection-of-two-linked-lists/}
3
 * Definition for singly-linked list.
4
 * function ListNode(val) {
5
 *     this.val = val;
6
 *     this.next = null;
7
 * }
8
 */
9

10
/**
11
 * @param {ListNode} headA
12
 * @param {ListNode} headB
13
 * @return {ListNode}
14
 */
15
var getIntersectionNode = function (headA, headB) {
16
    if (headA === null || headB === null) {
17
        return null;
18
    }
19

20
    let pA = headA, pB = headB;
21
    while (pA !== pB) {
22
        pA = pA === null ? headB : pA.next;
23
        pB = pB === null ? headA : pB.next;
24
    }
25

26
    return pA;
27
};