LeetCode如何求两个链表的第一个公共节点
求两个链表的第一个公共节点,可以使用双指针的方法来解决这个问题。
## 一、概述
要找到两个链表的第一个公共节点,我们需要从头开始遍历两个链表。由于两个链表可能不一样长,我们需要先找到两个链表的长度差,然后让长链表的指针先移动长度差的步数,然后再同时移动两个指针,直到找到第一个相同的节点。
## 二、查找链表长度差
为了找到两个链表的长度差,我们可以分别遍历两个链表并统计节点个数。然后根据节点个数的差值,让较长链表的指针先移动差值的步数。
具体的做法如下:
1. 初始化两个指针`p1`和`p2`分别指向两个链表的头节点;
2. 创建两个变量`len1`和`len2`用于记录两个链表的长度;
3. 分别遍历两个链表,每遍历一个节点,长度加1;
4. 比较`len1`和`len2`的大小,如果`len1 > len2`,则让`p1`先移动`len1 - len2`步,否则让`p2`先移动`len2 - len1`步;
代码示例:
function getIntersectionNode(headA, headB) {
let p1 = headA;
let p2 = headB;
let len1 = 0;
let len2 = 0;
// 统计链表的长度
while(p1) {
len1++;
p1 = p1.next;
}
while(p2) {
len2++;
p2 = p2.next;
}
// 让较长链表的指针先移动长度差的步数
p1 = headA;
p2 = headB;
if(len1 > len2) {
for(let i = 0; i < len1 - len2; i++) {
p1 = p1.next;
}
} else {
for(let i = 0; i < len2 - len1; i++) {
p2 = p2.next;
}
}
// 同时移动两个指针,直到找到第一个相同的节点
while(p1 !== p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
## 三、寻找第一个公共节点
在上一步中,我们已经通过让较长链表的指针先移动了长度差的步数,现在我们只需要同时移动两个指针,直到找到第一个相同的节点。
具体的做法如下:
1. 分别遍历两个链表,每次将两个指针分别移动到下一个节点;
2. 当遇到两个指针相同时,即找到了第一个公共节点,返回该节点;
代码示例:
function getIntersectionNode(headA, headB) {
let p1 = headA;
let p2 = headB;
// 同时移动两个指针,直到找到第一个相同的节点
while(p1 !== p2) {
p1 = p1.next;
p2 = p2.next;
// 如果两个指针都为空,说明没有公共节点,返回null
if(p1 === null && p2 === null) return null;
// 如果p1为空,则将其指向headB;如果p2为空,则将其指向headA
p1 = p1 === null ? headB : p1;
p2 = p2 === null ? headA : p2;
}
return p1;
}
通过以上方法,我们可以在O(m+n)的时间复杂度内找到两个链表的第一个公共节点,其中m和n分别是两个链表的长度。
猜您想看
-
油猴脚本安全技巧:使用 HTTPS Everywhere 插件加强安全性
如何使用HTT...
2023年05月13日 -
arcmap如何合并数据
准备合并的数据...
2023年06月26日 -
如何用Python爬取B站上1.4w条马老师视频数据来分析
如何使用Pyt...
2023年07月20日 -
如何在宝塔面板中重启PHP?
如何在宝...
2023年04月16日 -
rocketmq部署启动指南
准备工作在部署...
2023年07月22日 -
如何在Docker中进行备份和恢复?
如何在Dock...
2023年04月16日