双指针
解题思路
A+B === B+A，用双指针 pA 、pB 循环两个链表，链表 A 循环结束就循环链表 B，链表 B 循环结束就循环链表 A；当pA == pB时就是交点，因为两个指针移动的步数一样；示例：相交链表
- AB表：[1, 2, 3, 7, 8, 9 | 4, 5, 7, 8, 9]
- BA表：[4, 5, 7, 8, 9 | 1, 2, 3, 7, 8, 9]
示例：不相交链表
- AB表：[1, 2, 3 | 4, 5]
- BA表：[4, 5 | 1, 2, 3]
复杂度
-
时间复杂度：
O(m+n)，m、n 分别是两个链表的长度； -
空间复杂度：
O(1)
代码实现
var getIntersectionNode = function (headA, headB) {
if (headA === null || headB === null) return null;
let pA = headA, pB = headB;
// pA === pB 的时候有两种情况：
// 1.有相交的时候 pA、pB 为 相交节点
// 2.没有相交的时候 pA、pB 为 null
while (pA !== pB) {
pA = pA === null ? headB : pA.next; // 链表A循环结束就循环链表B
pB = pB === null ? headA : pB.next; // 链表B循环结束就循环链表A
}
return pA; // 当pA == pB时就是交点
};
哈希
解题思路
将链表 A 存入 set 中，再迭代链表 B ，判断节点是否在 set 中存在；
第一个相同的节点就是重合的节点；
复杂度
-
时间复杂度：
O(m+n)，m、n 分别是两个链表的长度； -
空间复杂度：
O(m)；
代码实现
var getIntersectionNode = function (headA, headB) {
let set = new Set;
while (headA) {
set.add(headA);
headA = headA.next;
}
while (headB) {
if (set.has(headB)) return headB;
headB = headB.next;
}
return null;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 142. 环形链表 II
上一篇
评论
