盒子
盒子
文章目录
  1. 暴力解题
  2. 快慢指针和双指针
  3. 使用map
  4. 总结

打印两个链表的第一个公共节点

力扣上剑指offer52,打印两个链表的第一个公共节点。

举个栗子

很多问题都有多种算法可以解决。

暴力解题

最最最简单的就是暴力解题,你说两个链表的第一个公共节点,那好,我就挨个遍历就完事了。

对于A链表中的每个节点,都遍历B链表,如果有相同的节点,则返回该节点。

代码就不写了,毕竟没人会看效率最低的代码。

假设链表A长度为n,链表B长度为m,时间复杂度大约为O(nm),空间复杂度O(1)。

还有一种是借助额外的空间,使用两个栈。将两个链表中的节点全都入栈,判断两个栈顶元素,如果相同则出栈;如果不同则返回刚出栈的元素。

时间复杂度为O(n+m),空间复杂度(n+m)

快慢指针和双指针

快慢指针是两个指针,先让快指针走一段距离,然后快慢指针以同样的速度走。

题目没有实现直接获取链表长度的方法,所以需要先遍历分别遍历两个链表一次,才能知道哪个链表长。之后再进行实际的快慢指针。

这里我们可以先做一个互补操作,使两个链表长度相等,但实际上我们不需要生成如下的链表,只需要遍历完一条链表后指向另一条链表的表头即可。

链表互补

链表互补之后,链表长度相等,双指针同时前进直接遍历。如果最后有相同部分,说明两个链表相交,如果没有相同部分,则说明两个链表没有交点,返回null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/

/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
if (headA || headB) {
return null;
}

let h1 = headA;
let h2 = headB;

while (h1 !== h2) {
h1 = h1 == null ? h2 : h1.next;
h2 = h2 == null ? h1 : h2.next;
}

return h1;
};

这样下来时间复杂度为O(n+m),空间复杂度O(1)

使用map

map是ES6的数据结构,可以保存键值对。

我们遍历一条链表,将所有的节点的值都设为true,然后遍历另一条链表,访问map对象,判断map中是否存在该节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
const map = new Map();
let h1 = headA
while (h1) {
map.set(h1, true);
h1 = h1.next;
}

let h2 = headB
while (h2) {
if (map.has(h2)) return h2;
h2 = h2.next;
}

return null;
};

这个算法需要先创建一个map对象,存放n个节点,空间复杂度是O(n)。

向map中添加添加元素需要遍历一次链表a,然后再遍历链表b判断是否存在该节点,时间复杂度是O(n+m)。

总结

最优解是双指针解法,时间复杂度为O(N)级,空间复杂度为O(1)常数级。

欢迎关注公众号
扫码关注我的微信公众号-大前端合集
  • 微信公众号-大前端合集