【忍者算法】从十字路口相遇到链表交点：探索相交链表问题｜LeetCode第160题 相交链表

从十字路口相遇到链表交点：探索相交链表问题

生活中的相遇问题

想象两个人从不同的地方出发，最后在一个十字路口相遇。他们可能走过不同长度的路程，但最终会在同一个点汇合。这就很像我们今天要讨论的相交链表问题：两个链表从不同的起点出发，在某个节点相交，然后共享后续的路径。
问题描述

LeetCode第160题"相交链表"是这样描述的：给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
例如：

1. A链表：      a1 → a2
2.                     ↘
3.                       c1 → c2 → c3
4.                     ↗            
5. B链表： b1 → b2 → b3
7. 输出：返回节点c1

复制代码

最直观的解法：哈希表记录

就像在一个城市里标记每个人走过的地方，最简单的方法是用一个哈希表记录第一个人走过的所有位置，然后看第二个人的路径中是否有重复的地方。
哈希表方法的实现

1. public class Solution {
2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3.         // 使用HashSet记录链表A中的所有节点
4.         Set<ListNode> visited = new HashSet<>();
5.         
6.         // 遍历链表A，将节点加入集合
7.         ListNode current = headA;
8.         while (current != null) {
9.             visited.add(current);
10.             current = current.next;
11.         }
12.         
13.         // 遍历链表B，查找第一个在集合中出现的节点
14.         current = headB;
15.         while (current != null) {
16.             if (visited.contains(current)) {
17.                 return current;
18.             }
19.             current = current.next;
20.         }
21.         
22.         return null;
23.     }
24. }

复制代码

优化解法：双指针技巧

仔细思考，我们发现一个有趣的现象：如果两个人分别走对方的路，他们最终一定会相遇！这就是双指针解法的灵感来源。
双指针方法的原理

想象两个人在散步：

• A从链表A出发，走完后转到链表B继续走
  
• B从链表B出发，走完后转到链表A继续走
  
• 如果链表相交，他们一定会在相交点相遇
  
  
  
  • 因为他们走过的总路程是相同的：链表A长度 + 链表B长度
    
  
  

示例运行

假设链表A：1→2→3→4，链表B：5→6→3→4（3是相交点）

1. 指针A：1 → 2 → 3 → 4 → 5 → 6 → [3] ← 相遇！
2. 指针B：5 → 6 → 3 → 4 → 1 → 2 → [3] ← 相遇！

复制代码

Java代码实现

1. public class Solution {
2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3.         if (headA == null || headB == null) {
4.             return null;
5.         }
6.         
7.         // 初始化两个指针
8.         ListNode pointerA = headA;
9.         ListNode pointerB = headB;
10.         
11.         // 当两个指针不相等时继续移动
12.         while (pointerA != pointerB) {
13.             // 移动指针A，如果到达末尾则转到链表B
14.             pointerA = (pointerA == null) ? headB : pointerA.next;
15.             // 移动指针B，如果到达末尾则转到链表A
16.             pointerB = (pointerB == null) ? headA : pointerB.next;
17.         }
18.         
19.         // 返回相交点（如果不存在相交点，两个指针都会是null）
20.         return pointerA;
21.     }
22. }

复制代码

解法比较

让我们比较这两种方法：
哈希表法：

• 时间复杂度：O(m+n)
  
• 空间复杂度：O(m)，m为链表A的长度
  
• 优点：思路直观，容易理解
  
• 缺点：需要额外的空间存储节点
  

双指针法：

• 时间复杂度：O(m+n)
  
• 空间复杂度：O(1)
  
• 优点：不需要额外空间，优雅简洁
  
• 缺点：理解起来稍微有点难度
  

实用技巧总结

解决链表相交问题的关键点：

• 理解相交后的节点都是共享的
  
• 考虑特殊情况（如空链表、不相交的情况）
  
• 善用双指针技巧
  
• 利用数学特性（路程相等原理）
  

相关的链表问题：

• 判断链表是否有环
  
• 找到链表环的入口
  
• 链表的中间节点
  

小结

通过相交链表这道题，我们学会了如何巧妙地使用双指针技巧来解决看似复杂的问题。这种思维方式不仅能解决算法题，在处理数据流、文件比较等实际问题时也很有用。记住，当遇到需要找到两个序列共同元素的问题时，双指针技巧往往能提供一个优雅的解决方案！
延伸思考：

• 如果链表可能有环，这个算法还有效吗？
  
• 如果要找到所有的相交节点，应该如何修改算法？
  
• 在分布式系统中，如何处理类似的"路径相交"问题？
  

作者：忍者算法
公众号：忍者算法


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！