L22.【LeetCode笔记】相交链表(新版)

1.题目

代码模板

2.分析

编辑算法误区

正确方法1

但不能通过所有的测试用例

修改后

提交结果

正确方法2

节省代码的技巧

1.题目

https://leetcode.cn/problems/3u1WK4/description/

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '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
输出：Intersected at '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 。
提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

注意：本题与主站 160 题相同：160. 相交链表 - 力扣（LeetCode）

代码模板

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{   
}

2.分析

旧版分析见L10.【LeetCode笔记】环形链表(判断链表中是否有环)(旧版)文章

读题可知,对于两个链表相交可能有以下三种情况

中间节点相交

头结点相交(下图为A链表的中间节点和B链表的头节点相交)

尾节点相交

但绝对不存在“X”形的相交情况,一个节点只能有一个next指针

算法误区

设两个指针p1和p2分别从A和B链表的头节点出发,不能通过p1->val==p2->val来判断到达了相交节点,会对不相交的链表造成误判

正确方法1

将A链表的每个节点的地址和B链表的所有节点的地址进行比较,如果相等则可求出相交节点的地址

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode * pA=headA;struct ListNode * pB=headB;while(pA!=pB){if (pB==NULL){pB=headB;pA=pA->next;}if (pA==NULL)return NULL;pB=pB->next;}return pA;
}

但不能通过所有的测试用例

原因:pB->next==NULL,因此pB=pB->next为pB=NULL->next,不合法,尾部相交会出问题

修改后

其实只需要交换下判断的顺序即可

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode * pA=headA;struct ListNode * pB=headB;while(pA!=pB){if (pA==NULL)return NULL;pB=pB->next;if (pB==NULL){pB=headB;pA=pA->next;}}return pA;
}

提交结果

这种方法时间复杂度为 $O(M*N)$ ,不推荐使用

正确方法2

双指针算法时间复杂度为 $O(N)$ ,参见L7.【LeetCode笔记】相交链表(旧版)

其实双指针的代码还可以写的更简洁些

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode * tailA=headA;struct ListNode * tailB=headB;int lenA=1;int lenB=1;//求A和B链表的长度while (tailA->next){tailA=tailA->next;lenA++;}while (tailB->next){tailB=tailB->next;lenB++;}//两个while循环结束后,tailA和tailB分别指向各自链表的尾部节点if (tailA!=tailB)return NULL;//非尾部相交,返回NULL//头部相交和中间相交的情况int distance=abs(lenA-lenB);//假设A链表为长链表,B链表为短链表struct ListNode * longlist=headA;struct ListNode * shortlist=headB;//假设不成立再更正,节省代码if (lenA<lenB){longlist=headB;shortlist=headA;} while (distance--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}