打印两个链表的第一个公共节点
「力扣上剑指offer52，打印两个链表的第一个公共节点。」
举个栗子
很多问题都有多种算法可以解决。
暴力解题
最最最简单的就是暴力解题，你说两个链表的第一个公共节点，那好，我就挨个遍历就完事了。
对于A链表中的每个节点，都遍历B链表，如果有相同的节点，则返回该节点。
代码就不写了，毕竟没人会看效率最低的代码。
「假设链表A长度为n，链表B长度为m，时间复杂度大约为O(nm)，空间复杂度O(1)。」
还有一种是借助额外的空间，使用两个栈。将两个链表中的节点全都入栈，判断两个栈顶元素，如果相同则出栈；如果不同则返回刚出栈的元素。
「时间复杂度为O(n+m)，空间复杂度(n+m)」
快慢指针和双指针
快慢指针是两个指针，先让快指针走一段距离，然后快慢指针以同样的速度走。
题目没有实现直接获取链表长度的方法，所以需要先遍历分别遍历两个链表一次，才能知道哪个链表长。之后再进行实际的快慢指针。
这里我们可以先做一个互补操作，使两个链表长度相等，但实际上我们不需要生成如下的链表，只需要遍历完一条链表后指向另一条链表的表头即可。
链表互补
链表互补之后，链表长度相等，双指针同时前进直接遍历。如果最后有相同部分，说明两个链表相交，如果没有相同部分，则说明两个链表没有交点，返回null。
/**
* 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中是否存在该节点。
/**
* @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)常数级。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录