知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 23 - 相交链表 ## 题目(LeetCode 160) 找到两个链表相交的起始节点。 ## 解法:双指针 ```java class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA, b = headB; while (a != b) { a = (a != null) ? a.next : headB; b = (b != null) ? b.next : headA; } return a; } } ``` > 💬 **Q:给出示例说明** > > 核心思想:**两个指针各走一遍对方的路,总路程相同,必然在交点相遇。** > > ``` > 链表 A:a1 → a2 → c1 → c2 → c3 > 链表 B:b1 → b2 → b3 → c1 → c2 → c3 > ↑ 交点 > > A 的长度 = 2(独有)+ 3(公共)= 5 > B 的长度 = 3(独有)+ 3(公共)= 6 > > 指针 a 走的路(走完 A 后切换到 B 的头): > a1 → a2 → c1 → c2 → c3 → null → b1 → b2 → b3 → [c1] > 步数:2 + 3 + 3 = 8 > > 指针 b 走的路(走完 B 后切换到 A 的头): > b1 → b2 → b3 → c1 → c2 → c3 → null → a1 → a2 → [c1] > 步数:3 + 3 + 2 = 8 > > 两者都走了 8 步,同时到达 c1(交点),a == b,循环结束 ✓ > ``` > > 数学本质:`A独有 + 公共 + B独有 = B独有 + 公共 + A独有`,两边相等,所以必然同时到达交点。 > > **没有交点的情况:** > > ``` > 链表 A:a1 → a2 → a3 > 链表 B:b1 → b2 > > 指针 a:a1→a2→a3→null→b1→b2→null > 指针 b:b1→b2→null→a1→a2→a3→null > > 两者同时走到 null,a == b == null,循环结束,返回 null ✓ > ``` ## 复杂度 - 时间 O(m+n),空间 O(1) ## 一句话总结 两个指针各走一遍两条链表,路程相同必在交点相遇(或同时到 null)。 ## 说明 相交链表的双指针解法(两个指针各走两条链表)是最优解,O(m+n) 时间 O(1) 空间。 HashSet 记录已访问节点也可以解决,但空间 O(m)。当前双指针解法已是最优,且思路非常巧妙。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入