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 // 两条链表没有相交点代码支持JSJS 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 为: A C链表 2 为: B C其中 A、B 分别为两条链表相交前的独立部分C 为共用部分。当 a 指针将链表 1 遍历完后重定位到链表 B 的头结点然后继续遍历直至相交点a 指针遍历的总距离为 A C B。同理 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, PHPJS 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 Codeclass 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 aGo Code:/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func getIntersectionNode(headA, headB *ListNode) *ListNode { // aA(a单独部分)C(a相交部分); bB(b单独部分)C(b相交部分) // abbaACBCBCAC 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)$仅使用两个指针变量无额外数据结构。实现要点与边界条件PHP 中必须使用!而非!!在 PHP 中是宽松比较两个值为null的对象会被视为相等可能提前误判使用!严格比较才能保证在真正遇到相同节点或同时到达null时退出。空指针重定位时机只有当指针走到null时才重定位到另一条链表的头结点否则直接前移一步。若两条链表长度恰好相等且不相交两指针会在第一轮末尾同时为null并退出返回null。相交后是共用节点而非值相等本题判定的核心是节点引用是否相同因此 Go 中直接比较*ListNode指针、JS 中直接比较对象引用都是可行的而 Python 中a ! b对 ListNode 默认比较对象身份同样成立。返回值的语义相交时返回交点节点不相交时返回null与题目要求一致。两种解法对比与延伸对比维度解法一哈希法解法二双指针时间复杂度$O(N)$$O(N)$空间复杂度$O(N)$$O(1)$思路难度直观容易想到需要证明与积累实现语言任意语言均易实现需要注意语言间比较语义差异从工程实践角度看双指针解法在空间上更优是面试中更受青睐的答案而哈希法思路直白作为第一反应可以快速给出正确解再优化为双指针。相关延伸与仓库配套资源本题在仓库中被收录于 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 题解 160. 相交链表：哈希法与双指针双解法深度解析（含正确性证明与 JS/Python/Go/PHP 实现）
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 // 两条链表没有相交点代码支持JSJS 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 为: A C链表 2 为: B C其中 A、B 分别为两条链表相交前的独立部分C 为共用部分。当 a 指针将链表 1 遍历完后重定位到链表 B 的头结点然后继续遍历直至相交点a 指针遍历的总距离为 A C B。同理 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, PHPJS 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 Codeclass 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 aGo Code:/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func getIntersectionNode(headA, headB *ListNode) *ListNode { // aA(a单独部分)C(a相交部分); bB(b单独部分)C(b相交部分) // abbaACBCBCAC 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)$仅使用两个指针变量无额外数据结构。实现要点与边界条件PHP 中必须使用!而非!!在 PHP 中是宽松比较两个值为null的对象会被视为相等可能提前误判使用!严格比较才能保证在真正遇到相同节点或同时到达null时退出。空指针重定位时机只有当指针走到null时才重定位到另一条链表的头结点否则直接前移一步。若两条链表长度恰好相等且不相交两指针会在第一轮末尾同时为null并退出返回null。相交后是共用节点而非值相等本题判定的核心是节点引用是否相同因此 Go 中直接比较*ListNode指针、JS 中直接比较对象引用都是可行的而 Python 中a ! b对 ListNode 默认比较对象身份同样成立。返回值的语义相交时返回交点节点不相交时返回null与题目要求一致。两种解法对比与延伸对比维度解法一哈希法解法二双指针时间复杂度$O(N)$$O(N)$空间复杂度$O(N)$$O(1)$思路难度直观容易想到需要证明与积累实现语言任意语言均易实现需要注意语言间比较语义差异从工程实践角度看双指针解法在空间上更优是面试中更受青睐的答案而哈希法思路直白作为第一反应可以快速给出正确解再优化为双指针。相关延伸与仓库配套资源本题在仓库中被收录于 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考