一、题目描述给定两个单链表的头节点headA和headB找出并返回两个链表相交的起始节点。如果不存在相交节点返回null。示例输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at 8图示A: 4 → 1 → 8 → 4 → 5 ↑ B: 5 → 6 → 1 ←←←←←←←←二、核心思路关键观察两个链表长度可能不同但相交后的部分长度相同。如果我们让两个指针分别走完自己的链表后再走对方的链表它们最终会在相交点相遇或同时走到NULL无相交A: a₁ → a₂ → c₁ → c₂ → c₃ → NULL B: b₁ → b₂ → b₃ → c₁ → c₂ → c₃ → NULL ↑ ↑ 这里相遇数学证明设 A 独有长度 aB 独有长度 b公共部分长度 c指针 pA 走a c b指针 pB 走b c a两者相等一定会同时走完三、代码实现方法一双指针法最优解✅/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){structListNode*pAheadA;structListNode*pBheadB;while(pA!pB){// A 走完换 BB 走完换 ApApA?pA-next:headB;pBpB?pB-next:headA;}returnpA;// 可能为 NULL无相交}代码图解初始 A: 4 → 1 → 8 → 4 → 5 B: 5 → 6 → 1 → 8 → 4 → 5 pAA头, pBB头 第1步pA1, pB1不相等继续 第2步pA8, pB8相遇返回8复杂度分析复杂度值时间O(m n)空间O(1)四、其他解法方法二哈希集合structListNode*getIntersectionNode_hash(structListNode*headA,structListNode*headB){structListNode*pAheadA;// C 语言需要用数组模拟哈希这里省略实现// 思路遍历 A将所有节点入 set// 遍历 B第一个在 set 中的就是相交点}复杂度值时间O(m n)空间O(m) 或 O(n)⚠️ C 语言实现较繁琐且不满足 O(1) 空间要求。方法三先求长度差// 1. 求链表长度intgetLength(structListNode*head){intlen0;while(head){len;headhead-next;}returnlen;}structListNode*getIntersectionNode_length(structListNode*headA,structListNode*headB){intlenAgetLength(headA);intlenBgetLength(headB);// 让长的链表先走差距步while(lenAlenB){headAheadA-next;lenA--;}while(lenBlenA){headBheadB-next;lenB--;}// 同时走知道相遇while(headA!headB){headAheadA-next;headBheadB-next;}returnheadA;}复杂度值时间O(m n)空间O(1)五、方法对比方法时间空间代码简洁度双指针O(mn)O(1) ⭐⭐⭐⭐ 最简洁哈希集合O(mn)O(m)⭐⭐ 需额外数据结构长度差O(mn)O(1)⭐⭐ 需两次遍历六、双指针法的本质走过的路一样长就一定会相遇情况结果有相交相遇于交点无相交同时走到 NULL七、总结本题的关键是想到让两个指针走完自己的链表后再走对方的链表这样就能消除长度差。代码非常简洁优雅while(pA!pB){pApA?pA-next:headB;pBpB?pB-next:headA;}