当前位置：首页 > ds >正文

LeetCode -160.相交链表

ds 2025/5/1 21:24:50

题目

160. 相交链表 - 力扣（LeetCode）

解法一

哈希表

哈希表解决方案的思路

这个使用哈希表（unordered_set）的解决方案基于一个简单的观察：如果两个链表相交，那么相交点及之后的所有节点都是两个链表共有的。

算法步骤

创建一个哈希表（unordered_set）来存储链表A中的所有节点的地址
遍历链表A，将每个节点的地址加入哈希表
遍历链表B，对于每个节点检查其地址是否已经在哈希表中
如果找到一个已经在哈希表中的节点，那么它就是第一个相交点
如果遍历完链表B都没有找到相交点，返回nullptr

代码

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB)return nullptr;unordered_set<ListNode*>nodeSet;while(headA){nodeSet.insert(headA);headA = headA->next;}while(headB){if(nodeSet.count(headB)){return headB;}headB = headB->next;}return nullptr;}
};

易错点

既然是要查找哈希表中是否存在某个节点，可能第一印象会去使用find方法，但是这样是不行的，使用了 find() 方法的返回值作为条件判断，而 unordered_set::find() 返回的是一个迭代器，不是布尔值，所以不能直接用在 if 条件中。要使用nodeSet.count()，不能使用nodeSet.find方法。

解法二

双指针

双指针方法的原理

这个方法基于一个重要的数学性质：如果两个链表相交，那么从某个节点开始，它们的后续节点都是共享的。

假设：

链表A长度为a+c，其中a是相交点前的长度，c是共享部分的长度
链表B长度为b+c，其中b是相交点前的长度，c是共享部分的长度

如果我们让两个指针分别从链表A和链表B的头部开始，当一个指针到达链表末尾时，将其重定向到另一个链表的头部继续遍历，那么：

指针ptrA走的路径为：a+c+b
指针ptrB走的路径为：b+c+a

可以看到，两个指针走的总路径长度相同，都是a+b+c。这意味着它们必然会同时到达相交点。

算法步骤

初始化：
- 创建两个指针ptrA和ptrB，分别初始化为链表A和链表B的头节点
遍历链表：
- 当ptrA不等于ptrB时，持续循环
- 在每次迭代中：
  - 如果ptrA不为nullptr，则移动到下一个节点；否则，将其指向链表B的头节点
  - 如果ptrB不为nullptr，则移动到下一个节点；否则，将其指向链表A的头节点
结束条件：
- 循环结束时，ptrA和ptrB要么都指向相交点，要么都为nullptr（表示没有相交点）
返回结果：
- 返回ptrA（或ptrB，它们此时指向同一个节点或都为nullptr）

图解示例

假设

链表A：a1→a2→c1→c2→c3
链表B：b1→b2→b3→c1→c2→c3

ptrA的路径：a1→a2→c1→c2→c3→null→b1→b2→b3→c1（在c1处相遇）

ptrB的路径：b1→b2→b3→c1→c2→c3→null→a1→a2→c1（在c1处相遇）

为什么这个方法有效

处理长度差异：通过让指针"跳转"到另一个链表，我们自动处理了两个链表长度的差异
保证相遇：
- 如果有相交点，两个指针会在走完a+b+c的路径后同时到达相交点
- 如果没有相交点(c=0)，两个指针会在走完a+b的路径后同时变为nullptr
时间复杂度O(n)：最多遍历两次链表长度的和
空间复杂度O(1)：只使用了两个指针变量，不需要额外空间

代码

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* ptrA = headA;ListNode* ptrB = headB;while(ptrA!=ptrB){ptrA == nullptr ? ptrA = headB : ptrA = ptrA->next;ptrB == nullptr ? ptrB = headA : ptrB = ptrB->next;}return ptrA;}
};