【代码随想录 | Leetcode | 第七天】链表 | 链表相交 | 环形链表 II

迈不过友情╰ 2023-10-13 19:43 28阅读 0赞

## 前言 ##

**欢迎来到[小K][K]的[Leetcode|代码随想录|专题化][Leetcode]专栏，今天将为大家带来链表相交和环形链表 II的分享**✨

#### 目录 ####

*  前言
 *  面试题 02.07. 链表相交
 *  142. 环形链表 II
 *  总结

--------------------

## 面试题 02.07. 链表相交 ##

✨[题目链接点这里][Link 1]

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

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

![在这里插入图片描述][29c12ee44f7b463991488d4dc6e1de24.png]

**题目数据 保证 整个链式结构中不存在环。  
注意，函数返回结果后，链表必须 保持其原始结构 。**

示例 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]`  
**思路：这道题目也是双指针的一种用法，我们先定义两个指针分别指向两个链表的头结点，然后让指向较长链表的指针朝后移动，和较短链表的那个指针对其，最后就是移动，循环比较，返回第一个 两个指针指向同一节点的情况，没找到则返回空**

class Solution {
        
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
            ListNode* curA = headA, *curB = headB;
            int lenA = 0, lenB = 0;
            while (curA != nullptr) {
        
                lenA++;
                curA = curA->next;
            }
            while (curB != nullptr) {
        
                lenB++;
                curB = curB->next;
            }
            curA = headA;
            curB = headB;
            if (lenA < lenB){
        
                swap(lenA,lenB);
                swap(curA,curB);
            }
            int gap = lenA - lenB;
            while (gap--) curA = curA->next;
            while (curA != nullptr) {
        
                if(curA == curB) return curA;
                curA = curA->next;
                curB = curB->next;
            }
            return nullptr;
        }
    };

![在这里插入图片描述][be8fd62772a54f5d97e91455b685d0d2.png]

## 142. 环形链表 II ##

✨[题目链接点这里][Link 2]  
**给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。  
不允许修改 链表。**

示例 1：  
![在这里插入图片描述][4e552bc2b3894c01bc206b1793d00eb3.png]

**输入**：head = \[3,2,0,-4\], pos = 1  
**输出**：返回索引为 1 的链表节点  
**解释**：链表中有一个环，其尾部连接到第二个节点。

示例 2：  
![在这里插入图片描述][aac328604b9245749de5824993df35d6.png]

**输入**：head = \[1,2\], pos = 0  
**输出**：返回索引为 0 的链表节点  
**解释**：链表中有一个环，其尾部连接到第一个节点。

示例 3：  
![在这里插入图片描述][47f3e217be774d4ebc314eac297e226c.png]

**输入**：head = \[1\], pos = -1  
**输出**：返回 null  
**解释**：链表中没有环。

提示：  
**链表中节点的数目范围在范围 \[0, 104\] 内**  
\-105 <= `Node.val` <= 105  
**pos 的值为 -1 或者链表中的一个有效索引**

思路：解决这个问题我们需要明确下面两个问题

*  判断链表是否有环
 *  如果有环，如何找到这个环的入口

> **问题一：判断链表是否有环**
> 
> > 可以使用快慢指针法，定义一个快指针 fast 和一个慢指针 slow ，从头结点开始，每次让快指针移动两个节点，慢指针每次移动一个节点，如果在途中相遇，则代表有环
> > 
> > > 相遇一定在环内相遇，这是为什么？**快指针一定比慢指针先入环**  
> > > 为什么快慢指针一定会相遇？**快指针一次移动两步，而慢指针一次移动一步，所以快指针相当于是以每次一步来追赶慢指针，所以一定会相遇**

![在这里插入图片描述][e38b051571414a37ab3147fdf87a4c3b.png]

> **问题二：找环的入口**
> 
> > 假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。  
> > 那么相遇时： slow指针走过的节点数为: `x + y`， fast指针走过的节点数：`x + y + n (y + z)`，n为fast指针在环内走了n圈才遇到slow指针， `（y+z）`为 一圈内节点的个数A  
> > **则有：(x + y) \* 2 = x + y + n (y + z)**  
> > **化简得x = (n - 1)(y + z) + z ，注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。**当n等于一和大于一的效果是一样的，因为当n大于一就相当于快指针在环内多转了几圈

class Solution {
        
    public:
        ListNode *detectCycle(ListNode *head) {
        
            ListNode* slow = head;
            ListNode* fast = head;
            while (fast != nullptr && fast->next != nullptr) {
        
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast) {
        
                    ListNode* index1 = head;
                    ListNode* index2 = fast;
                    while (index1 != index2) {
        
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index1;
                }
            }
            return nullptr;
        }
    };

![在这里插入图片描述][98be6c08e7424e599ccc3d23c1e0d491.png]

## 总结 ##

**今天的收获还是挺大的，这个环形链表不难，但是很有意思，有点写数学题的感觉，一步一步揭开面纱真的很舒服~**

[K]: https://blog.csdn.net/qq_72157449?spm=1000.2115.3001.5343
[Leetcode]: https://blog.csdn.net/qq_72157449/category_12293229.html?spm=1001.2014.3001.5482
[Link 1]: https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
[29c12ee44f7b463991488d4dc6e1de24.png]: https://img-blog.csdnimg.cn/29c12ee44f7b463991488d4dc6e1de24.png
[be8fd62772a54f5d97e91455b685d0d2.png]: https://img-blog.csdnimg.cn/be8fd62772a54f5d97e91455b685d0d2.png
[Link 2]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[4e552bc2b3894c01bc206b1793d00eb3.png]: https://img-blog.csdnimg.cn/4e552bc2b3894c01bc206b1793d00eb3.png
[aac328604b9245749de5824993df35d6.png]: https://img-blog.csdnimg.cn/aac328604b9245749de5824993df35d6.png
[47f3e217be774d4ebc314eac297e226c.png]: https://img-blog.csdnimg.cn/47f3e217be774d4ebc314eac297e226c.png
[e38b051571414a37ab3147fdf87a4c3b.png]: https://img-blog.csdnimg.cn/e38b051571414a37ab3147fdf87a4c3b.png
[98be6c08e7424e599ccc3d23c1e0d491.png]: https://img-blog.csdnimg.cn/98be6c08e7424e599ccc3d23c1e0d491.png