【剑指Offer刷题】——两个链表的第一个公共节点（52）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【剑指Offer刷题】——两个链表的第一个公共节点（52），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2625字，纯文字阅读大概需要4分钟。
内容图文
Leetcode刷题地址：https://leetcode-cn.com/problemset/lcof/
题目
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA
= 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为
[5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3,
skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2
（注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A
中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB
= 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n)
时间复杂度，且仅用 O(1) 内存。 本题与主站 160
题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
Solution 1
首先计算两个链表的长度，然后计算它们的差值dis，即为其中一个链表比另一个链表长的那部分。那么让长的那个链表先走dis，然后两个链表再同步走，直到相遇。
时间：O(n+m)，n和m分别为两个链表的长度；空间：O(1)。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL) return NULL;
ListNode* l1 = headA;
ListNode* l2 = headB;
int l1Length = 0;
int l2Length = 0;
int dis = 0;
while (l1 && l2) {
l1 = l1->next;
l2 = l2->next;
l1Length++;
l2Length++;
}
while (l1) {
l1 = l1->next;
l1Length++;
}
while (l2) {
l2 = l2->next;
l2Length++;
}
dis = l1Length > l2Length ? l1Length - l2Length : l2Length - l1Length;
l1 = headA;
l2 = headB;
if (l1Length > l2Length) {
while (dis--) l1 = l1->next;
} else {
while (dis--) l2 = l2->next;
}
while (l1 != l2) {
l1 = l1->next;
l2 = l2->next;
}
return l1;
}
结果：
Solution 2
双链表，浪漫相遇。让两个指针走过同样长度的路程，那么它们两个就相遇了。即当任一个指针走到自己链表的结尾时，重新定位到另一个链表的开头，然后继续走，那么相遇时两个指针走过的路程就是一样的。
时间：O(n+m)，n和m分别为两个链表的长度；空间：O(1)。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* l1 = headA;
ListNode* l2 = headB;
while (l1 != l2) {
l1 = l1 == NULL ? headB : l1->next;
l2 = l2 == NULL ? headA : l2->next;
}
return l1;
}
结果：
内容总结
以上是互联网集市为您收集整理的【剑指Offer刷题】——两个链表的第一个公共节点（52）全部内容，希望文章能够帮你解决【剑指Offer刷题】——两个链表的第一个公共节点（52）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。