【忍者算法】从十字路口相遇到链表交点：探索相交链表问题｜LeetCode第160题 相交链表
从十字路口相遇到链表交点：探索相交链表问题生活中的相遇问题
想象两个人从不同的地方出发，最后在一个十字路口相遇。他们可能走过不同长度的路程，但最终会在同一个点汇合。这就很像我们今天要讨论的相交链表问题：两个链表从不同的起点出发，在某个节点相交，然后共享后续的路径。
问题描述
LeetCode第160题"相交链表"是这样描述的：给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
例如：
A链表： a1 → a2 ↘ c1 → c2 → c3 ↗ B链表： b1 → b2 → b3输出：返回节点c1最直观的解法：哈希表记录
就像在一个城市里标记每个人走过的地方，最简单的方法是用一个哈希表记录第一个人走过的所有位置，然后看第二个人的路径中是否有重复的地方。
哈希表方法的实现
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 使用HashSet记录链表A中的所有节点 Set<ListNode> visited = new HashSet<>(); // 遍历链表A，将节点加入集合 ListNode current = headA; while (current != null) { visited.add(current); current = current.next; } // 遍历链表B，查找第一个在集合中出现的节点 current = headB; while (current != null) { if (visited.contains(current)) { return current; } current = current.next; } return null; }}优化解法：双指针技巧
仔细思考，我们发现一个有趣的现象：如果两个人分别走对方的路，他们最终一定会相遇！这就是双指针解法的灵感来源。
双指针方法的原理
想象两个人在散步：
[*]A从链表A出发，走完后转到链表B继续走
[*]B从链表B出发，走完后转到链表A继续走
[*]如果链表相交，他们一定会在相交点相遇
[*]因为他们走过的总路程是相同的：链表A长度 + 链表B长度
示例运行
假设链表A：1→2→3→4，链表B：5→6→3→4（3是相交点）
指针A：1 → 2 → 3 → 4 → 5 → 6 → ← 相遇！指针B：5 → 6 → 3 → 4 → 1 → 2 → ← 相遇！Java代码实现
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } // 初始化两个指针 ListNode pointerA = headA; ListNode pointerB = headB; // 当两个指针不相等时继续移动 while (pointerA != pointerB) { // 移动指针A，如果到达末尾则转到链表B pointerA = (pointerA == null) ? headB : pointerA.next; // 移动指针B，如果到达末尾则转到链表A pointerB = (pointerB == null) ? headA : pointerB.next; } // 返回相交点（如果不存在相交点，两个指针都会是null） return pointerA; }}解法比较
让我们比较这两种方法：
哈希表法：
[*]时间复杂度：O(m+n)
[*]空间复杂度：O(m)，m为链表A的长度
[*]优点：思路直观，容易理解
[*]缺点：需要额外的空间存储节点
双指针法：
[*]时间复杂度：O(m+n)
[*]空间复杂度：O(1)
[*]优点：不需要额外空间，优雅简洁
[*]缺点：理解起来稍微有点难度
实用技巧总结
解决链表相交问题的关键点：
[*]理解相交后的节点都是共享的
[*]考虑特殊情况（如空链表、不相交的情况）
[*]善用双指针技巧
[*]利用数学特性（路程相等原理）
相关的链表问题：
[*]判断链表是否有环
[*]找到链表环的入口
[*]链表的中间节点
小结
通过相交链表这道题，我们学会了如何巧妙地使用双指针技巧来解决看似复杂的问题。这种思维方式不仅能解决算法题，在处理数据流、文件比较等实际问题时也很有用。记住，当遇到需要找到两个序列共同元素的问题时，双指针技巧往往能提供一个优雅的解决方案！
延伸思考：
[*]如果链表可能有环，这个算法还有效吗？
[*]如果要找到所有的相交节点，应该如何修改算法？
[*]在分布式系统中，如何处理类似的"路径相交"问题？
<hr>作者：忍者算法
公众号：忍者算法
🎯 回复【刷题清单】获取更多经典题目解析
👥 回复【加群】加入算法/面试交流群，一起学习进步
🧑💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现
页:
[1]