企业官网建设流程全解析

LeetCode 题解 160. 相交链表：哈希法与双指针双解法深度解析（含正确性证明与 JS/Python/Go/PHP 实现）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇题解以 LeetCode 160. 相交链表（Intersection of Two Linked Lists）为核心，完整剖析哈希法与双指针两种解法，并给出双指针相遇点的严格数学证明，以及 JS、Python、Go、PHP 四种语言的可用代码。读完本文，你不仅能 AC 这道经典链表题，还能掌握"双链表交叉找交点"这类题目的通用思考框架，并与仓库内 双指针专题、链表专题 中的方法论相互印证。

题目描述

编写一个程序，找到两个单链表相交的起始节点。

相交链表是链表类问题中的经典题型，题目要求找出两条单链表从某个节点开始共用后续所有节点的那个"汇合点"。其难点在于：两条链表的长度可能不同，无法简单地同时从头遍历比较。

前置知识

• 链表
• 双指针

解法一：哈希法

核心思路

有 A、B 这两条链表，先遍历其中一个，比如 A 链表，并将 A 中的所有节点存入哈希表。随后遍历 B 链表，检查节点是否在哈希表中，第一个存在的就是相交节点。

该思路的本质是"用空间换时间"：由于链表节点在内存中是唯一的对象引用（在 C/C++ 等语言中即节点地址），只要 B 中的某个节点地址曾经出现在 A 中，就能确定两者从该节点开始发生相交。这里必须使用节点地址/引用而非节点值，因为相交的定义是物理上的节点共用，而非数值相等——这也是该解法中哈希表存储对象本身的原因。

伪代码

data = new Set() // 存放A链表的所有节点的地址 while A不为空{ 哈希表中添加A链表当前节点 A指针向后移动 } while B不为空{ if 如果哈希表中含有B链表当前节点 return B B指针向后移动 } return null // 两条链表没有相交点

代码支持：JS

JS Code:

let data = new Set(); while (A !== null) { data.add(A); A = A.next; } while (B !== null) { if (data.has(B)) return B; B = B.next; } return null;

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为两链表节点总数，需要各遍历一次。
• 空间复杂度：$O(N)$，哈希表需要额外存储 A 链表全部节点地址。

当两条链表不相交时，第二个 while 循环结束后返回null，与题目要求的"无交点返回 null"一致。

解法二：双指针

核心思路

使用 a、b 两个指针分别指向 A、B 这两条链表，两个指针以相同的速度向后移动：

• 当 a 到达链表的尾部时，重定位到链表 B 的头结点；
• 当 b 到达链表的尾部时，重定位到链表 A 的头结点；
• a、b 指针相遇的点即为相交的起始节点，若始终不相遇则两条链表没有相交点。

这个思路非常巧妙：它不需要知道两条链表各自有多长，而是通过"互相接龙"的方式让两个指针走过的总距离相等，从而在交点处"对齐"。

这一解法与仓库 91 算法基础篇双指针专题 中提到的双指针思想一脉相承——双指针不局限于左右端点、快慢指针，本题的双指针属于"同步速、换链续走"的变体，核心价值在于将两个独立链表的遍历合并为一次等长路径的追赶。

为什么 a、b 指针相遇的点一定是相交的起始节点？

我们证明一下：

1. 将两条链表按相交的起始节点继续截断，链表 1 为: A + C，链表 2 为: B + C（其中 A、B 分别为两条链表相交前的独立部分，C 为共用部分）。
2. 当 a 指针将链表 1 遍历完后，重定位到链表 B 的头结点，然后继续遍历直至相交点，a 指针遍历的总距离为 A + C + B。
3. 同理 b 指针遍历的总距离为 B + C + A。

由于 a、b 速度相同，而 $A + C + B = B + C + A$，两者走过的路径长度完全一致，因此在同一个时间点，它们必然同时"踏入"公共部分 C 的起点——也就是相交的起始节点，并在该点相遇。若两条链表不相交，则 a、b 最终会同时到达两条链表合并后的尾部（即都变为null），此时a == b == null，循环退出并返回null，恰好满足无交点时的语义。

伪代码

a = headA b = headB while a,b指针不相等时 { if a指针为空时 a指针重定位到链表 B的头结点 else a指针向后移动一位 if b指针为空时 b指针重定位到链表 A的头结点 else b指针向后移动一位 } return a

注意伪代码中的关键细节：指针为空时才重定位到另一条链表的头结点，其余情况每次只走一步；两条链表都不相交时，a、b 会在同时到达null时退出循环（此时a == b == null），返回a即返回null，无需特判。

代码支持：JS, Python, Go, PHP

JS Code:

var getIntersectionNode = function (headA, headB) { let a = headA, b = headB; while (a != b) { a = a === null ? headB : a.next; b = b === null ? headA : b.next; } return a; };

Python Code：

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: a, b = headA, headB while a != b: a = a.next if a else headB b = b.next if b else headA return a

Go Code:

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func getIntersectionNode(headA, headB *ListNode) *ListNode { // a=A(a单独部分)+C(a相交部分); b=B(b单独部分)+C(b相交部分) // a+b=b+a=A+C+B+C=B+C+A+C a := headA b := headB for a != b { if a == nil { a = headB } else { a = a.Next } if b == nil { b = headA } else { b = b.Next } } return a }

PHP Code:

/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */ class Solution { /** * @param ListNode $headA * @param ListNode $headB * @return ListNode */ function getIntersectionNode($headA, $headB) { $a = $headA; $b = $headB; while ($a !== $b) { // 注意, 这里要用 !== $a = $a ? $a->next : $headB; $b = $b ? $b->next : $headA; } return $a; } }

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为两链表节点总数，每个指针最多遍历两轮。
• 空间复杂度：$O(1)$，仅使用两个指针变量，无额外数据结构。

实现要点与边界条件

1. PHP 中必须使用!==而非!=：!=在 PHP 中是宽松比较，两个值为null的对象会被视为相等，可能提前误判；使用!==（严格比较）才能保证在真正遇到相同节点或同时到达null时退出。
2. 空指针重定位时机：只有当指针走到null时才重定位到另一条链表的头结点，否则直接前移一步。若两条链表长度恰好相等且不相交，两指针会在第一轮末尾同时为null并退出，返回null。
3. 相交后是"共用节点"而非"值相等"：本题判定的核心是节点引用是否相同，因此 Go 中直接比较*ListNode指针、JS 中直接比较对象引用都是可行的，而 Python 中a != b对 ListNode 默认比较对象身份，同样成立。
4. 返回值的语义：相交时返回交点节点；不相交时返回null，与题目要求一致。

两种解法对比与延伸

从工程实践角度看，双指针解法在空间上更优，是面试中更受青睐的答案；而哈希法思路直白，作为"第一反应"可以快速给出正确解，再优化为双指针。

相关延伸与仓库配套资源

本题在仓库中被收录于 README.md 的简单题（Easy）题单，同时在 collections/easy.md 中作为 91 天学算法基础篇的配套题目出现，适合与以下资源结合学习：

• 双指针专题（91 算法基础篇）：系统讲解快慢指针、左右端点指针、固定间距指针三类双指针套路，本题属于"等速双指针换链续走"的典型变体。
• 链表专题：覆盖链表插入、删除、遍历等基本操作的复杂度分析，帮助打好链表基本功。
• 142. 环形链表 II：同为"链表交点/入口"类问题，双指针思路与本题互相印证，可对比学习。
• 英文版题解：仓库同时提供英文版文档，便于对照学习专业术语。

掌握了本题的"双链对齐"思想后，遇到"判断两条链表是否相交""寻找相交节点"等变体题目（如 LeetCode 面试题中常见的变式），都可以复用同样的证明与代码框架。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode