【算法专题--链表】相交链表--高频面试题（图文详解，小白一看就会！！）

本文主要是介绍【算法专题--链表】相交链表--高频面试题（图文详解，小白一看就会！！），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、前言

二、题目描述 

三、解题方法

 ⭐双指针 --- 数学思维

 ⭐双指针 --- 按链表长度计算

🥝 判断相交

🍇 求出交点

🍍实现步骤 

四、总结与提炼

五、共勉 

---

一、前言

        相交链表这道题，可以说是--链表专题--，比较经典的一道题，也是在面试中频率较高的一道题目，通常在面试中，面试官可能会要求我们写出多种解法来实现这道题目，所以大家需要对这道题目非常熟悉哦！！
        本片博客就来详细的讲讲解一下 相交链表 的多种实现方法，让我们的面试变的更加顺利！！！

二、题目描述 

 题目连接：160. 相交链表 - 力扣（LeetCode）

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

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

 示例 1：

 示例 2：

 三、解题方法

 ⭐双指针 --- 数学思维

 解题思路：

•  通过找规律，我们可以发现，将 两个 链表 -- 连接 --起来，就可以找出 相交的节点

例如：

这两个 链表  值相同 ------- 代表同一节点， 0  ------代表空节点

• 链表 A：1 -> 2 -> 3 -> 7 -> 8 -> 9 
• 链表 B：4 -> 5-> 7 -> 8 -> 9 

连接  两个链表 ---- 表 与 表 之间用 0 隔开

• AB表 ：【1，2，3，7，8，9，0，4，5，7，8，9，0】
• BA表 ：【4，5，7，8，9，0，1，2，3，7，8，9，0】 

 观察连接后的两个表，可以发现 相交的部分整齐的排列在末尾 ---- 【7，8，9,  0】

 只需要逐个遍历 这两张表的节点，找出第一个 值相同 的节点即可

---

 如果没有相交，会出现 什么样的情况呢？

• 链表 A：1 -> 2 -> 3 
• 链表 B：4 -> 5

 连接  两个链表 ---- 表 与 表 之间用 0 隔开

• AB表 ：【1，2，3，0，4，5，0】
• BA表 ：【4，5，0，1，2，3，0】 

观察连接后的两个表，可以发现 相交的部分必然 为 ---- 【0】（NULL）

参照上面的 逻辑 ，返回首个 相同的节点，为空是符合题意（两个链表不相交） 

---

代码：

         在写代码 的时候，不可能往 链表中注入 空节点 ，所以我们可以通过一个指针，模拟遍历两个链表相交的过程，当指针指向 空的时候，重新指向另一个链表的头节点，否则就指向下一个节点。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 定义 两个指针 用来遍历 两个 链接表 ：  AB表  BA表ListNode* a = headA;ListNode* b = headB;// 找到第一个 相同的节点返回即可while(a!=b){// 遍历完 A 再去 遍历 Bif(a!=nullptr){a = a->next;}else{a = headB;}// 遍历完 B 再去 遍历 Aif(b!=nullptr){b = b->next;}else{b = headA;}}return a;}
};

 ⭐双指针 --- 按链表长度计算

这道题拆分的话，其实就是两步： 

1. 判断两个链表是否相交
2. 然后找出第一个交点 

 🥝 判断相交

首先要判断链表 A 和 链表 B 是否相交，那怎么判断呢？ 

A链表 找到 尾节点，B链表 也找到 尾节点。
 
当 尾节点 的地址相同时，就是 相交。
 
这种方法的时间复杂度为：O ( M + N ) 

🍇 求出交点

既然能判断链表是否相交了，那么如何找到交点呢？

也很简单，直接说方法：

1️⃣：求出 A链表 的长度 La，再求出 B链表 的长度 Lb；
2️⃣：如果 A链表 比 B链表 长，那么 A链表 先走 La - Lb 步；

3️⃣ ：当 A链表 走了 差距步 以后，再让 A链表 和 B链表 再一起走，第一个 地址 相等的就是交点。

注意： 

如果 B链表 比 A链表 长，那么让 B链表 先走 Lb - La 步；
为什么要用 长的 减去 短的？因为这样得到的结果才是一个 正数 呀，这两个相减得到的值就是 差距步。

🍍实现步骤 

• 既然判断相交要从 头节点 开始走到 尾节点，那么我们就重新定义两个指针 tailA 和 tailB 分别指向 链表A 和 链表B 的头节点，然后开始往后走；
•  tailA 先走，当 tailA 走到 尾节点 时，就停下来（动图演示👇）

 然后 tailB 再走，当 tailB 走到 尾节点 时，就停下来（动图演示👇）

注意：这里是走到 尾节点，也就是说当 尾节点 的 next 指向 NULL 时，就停下来。 

• 然后再把 tailA 和 tailB 进行比较，如果它们的 地址 相等，说明相交，就找交点；如果 地址 不相等，就返回 NULL；
• 既然 地址 相等，那我们就要找交点，但是得先求出 A链表 和 B链表 的长度；
• 定义两个整型 lenA 和 lenB，分别用来表示长度，初始值设为 1。

 计算 lenA 的过程👇

计算 lenB 的过程👇 

注意： 

为什么把 lenA 和 lenB 的 初始值设为 1 呢？
 
因为要求链表长度，也就是走到 尾节点 就结束了；

也就说从第一个节点开始计算，当走到 尾节点 时，就结束，相当于 尾节点 没有计算，所以就少算了 1 个。

•  然后就是求出 差距步，让 长 的链表先走 差距步，然后再一起走；
• 此时 lenB 大于 lenA，求出 差距步 为 1； 
• 所以我们重新定义两个指针，longtList 指向 B 的头节点，shortList 指向 A 的头节点，然后让 longList 先走 差距步，也就是先走 1步（动图演示👇） 

此时再让 longList 和 shortList 一起走，走到相等的位置就停下来（动图演示👇） 

注意： 

上面的图中给的链表是 B 长，A 短，但是实际情况有可能是 A 长，B 短；也有可能是 A 和 B 一样长；

所以我们要把长度进行判断，假设默认先设为 A 长，B 短；

如果 lenA 大于 lenB，那么假设成立，就求 差距步；

如果 lenA 小于 lenB，那么说明假设不成立，重新定义即可。

---

代码实现： 

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* tailA; tailA = headA;ListNode* tailB;tailB = headB;int lenA = 1;  // 存放A链表的长度int lenB = 1;  // 存放B链表的长度// A 链表找尾节点while(tailA->next!=nullptr){tailA = tailA->next;lenA++;}// B 链表找尾节点while(tailB->next!=nullptr){tailB = tailB->next;lenB++;}// 如果 尾地址不相等，就是不相交，返回空if(tailA!=tailB){return nullptr;}// 若相交，求交点// 链表长的先走 “差距步”，然后一起走ListNode* shortList = headA;  // 假设A短ListNode* longList = headB;   // 假设B长// 如果 A长于Bif(lenA>lenB){// 那么就交换一下longList = headA;shortList = headB;}// 求出差距步int gap = abs(lenA - lenB);// 长的先走差距步while(gap--){longList = longList->next;}// 然后同时走while(shortList!=nullptr && longList!=nullptr){// 相交if(shortList == longList){return shortList;}shortList = shortList->next;longList = longList->next;}return nullptr;}
};

 四、总结与提炼

        最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关链表相交的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握 

五、共勉 

       以下就是我对 链表相交 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！ 

这篇关于【算法专题--链表】相交链表--高频面试题（图文详解，小白一看就会！！）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---