系列专栏

《分治》

《模拟》

《Linux》

---

目录

1、题目链接

2、题目介绍

3、解法（双指针） 

 返回结果

算法正确性

时间复杂度

4、代码

---

1、题目链接

160. 相交链表 - 力扣（LeetCode）

2、题目介绍

​

3、解法（双指针） 

推荐题解：题解 - 力扣（LeetCode）

该题解中的图示过程非常清晰！

这道题目，类似于检测两个链表中是否存在环。--->针对有环问题 ---> 我们通常使用快慢指针解决。

那么本题，使用的就是快慢指针的一个变形，找到两个链表的相交点。

设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：
 

头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c 个节点；​

考虑构建两个节点指针 A​ , B 分别指向两链表头节点 headA , headB ，做如下操作：

• 指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a+(b−c)
• 指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b+(a−c)

如下式所示，此时指针 A , B 重合，这是因为两个指针都遍历了相同的节点数（包括重复遍历的部分），并有两种情况：

a+(b−c)=b+(a−c)

• 若两链表 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
• 若两链表 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。

 返回结果

返回 A（或 B，因为它们此时是相同的）作为相交节点的指针。

如果 A 和 B 没有相遇（都为 null 或指向不同的节点），则返回 null。但在这个算法中，由于我们是在两个链表之间循环遍历，所以它们要么相遇，要么在原始链表上同时到达末尾（然后重新遍历另一个链表），这种情况在逻辑上被视为不相交，因此实际上我们不需要显式地检查 null。

        

算法正确性

该算法的正确性基于这样一个事实：

如果两个链表相交，那么从两个链表的头节点出发，分别遍历到相交节点的路径长度之差一定等于两个链表长度之差。

当我们让一个指针到达链表末尾后重新指向另一个链表的头节点时，我们实际上是在“补齐这个长度差。

因此，两个指针最终会在相交节点上相遇。

时间复杂度

由于每个节点最多被访问两次（一次在其原始链表中，一次在另一个链表中），所以时间复杂度为 O(m + n)，其中 m 和 n 分别是两个链表的长度。

空间复杂度：

我们只使用了两个指针，所以空间复杂度为 O(1)。 

4、代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {//a+b-c//a-c+b//有公共的结点，c>0,ListNode* pa = headA;ListNode* pb = headB;while (pa != pb){if (pa == NULL)pa = headB;elsepa = pa->next;if (pb == NULL)pb = headA;elsepb = pb->next;}return pa;}
};

---

💗感谢阅读！💗

---