【数据结构与算法】相交链表、环形链表(判断是否有环)、环形链表(返回入环节点)

主页：HABUO🍁主页：HABUO

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

1.相交链表

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

示例：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

分析：拿到这个题，我们最直接的想法就是能不能用我们之前的思想去解决，我们之前大多都是双指针解决的题，那这个题能不能解决呢？答案是肯定的，我们先观察下，如果下面的那个长的链表把多的那一个走了，之后长短链表一块走不久遇到了嘛，诶就是这样😃， 前面我们做了很多快指针要多走几步的题型，在这里我们又遇到了。因此大致思想就是：1.我们需要先知道谁长谁短。2.长的先走完长的步数。3.之后长短一块走，直至地址相同便是相交的节点。

我们先计算两个链表的长度，具体如下：

//先求两个链表的长度，判断谁长谁短，长的长多少
Node* curA = headA;
Node* curB = headB;
int sizeA = 1;
int sizeB = 1;
while(curA)
{
    sizeA++;
    curA = curA->next;
}
while(curB)
{
    sizeB++;
    curB = curB->next;
}

之后就是判断谁长谁短，长的先走完长的步数，之后一起走。具体如下所示：

 //判断谁长
    if(sizeA > sizeB)
    {
        int lenth_sub = sizeA - sizeB;
        //长的先走长的步数
        while(lenth_sub--)
        {
            headA = headA->next;
        }
        //之后同时走
        while(headA != headB)
        {
            if(headA == NULL)
            return NULL;
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
    //同样道理
    else
    {
        int lenth_sub = sizeB - sizeA;
        while(lenth_sub--)
        {
            headB = headB->next;
        }
        while(headA != headB)
        {
            if(headA == NULL)
            return NULL;
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }

2.环形链表（判断是否有环）

题目：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例1：

输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。 

示例2：

 输入：head = [1], pos = -1

输出：false

解释：链表中没有环。 

分析：看到题我们还是同样的思想能不能用之前解题的方式解决，两个指针，一个快指针一个慢指针，要是有环，快指针是不是先进入环，当慢指针进环时，无论快指针走到哪，是不是就相当于在一个圆里面你追我赶了，只要快慢指针能相遇就说明链表里有环，如果快指针直接遍历完了整个链表后指向NULL，那就是没环。那这里就有了一个追上追不上的问题，虽然快指针走的快，它们之间的距离是逐渐缩小但是如果快靠近的时候跨过去了怎么办？因此必须这样的一个距离是一个单元一个单元缩小，不然无论是偶数还是奇数是不是都有可能永远遇不到，因为偶数如果每次缩小的距离都是奇数那么永远都遇不到， 奇数也是同样的道理。具体见下：

所以思想就是快指针走两步，慢指针走一步，只要遇到就是有环。实现如下：

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast = head , *slow = head;
    while(fast && fast->next)//fast和fast->next不能为NULL，因为fast要走两步
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)//遇到就是有环
        return true;
    }
    return false; //走到这就是fast或者fast->next为NULL说明遍历了整个链表因此也就没环
}

3.环形链表（返回入环节点） 

题目：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。不允许修改 链表。

示例1：

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

输入：head = [1], pos = -1

输出：返回 null

解释：链表中没有环。

分析：这个题是上一个题的进阶版，上个题只需判断有没有环，这个题不但要有环而且还要返回环的入口节点，怎么做呢？前面有个相交链表，这能不能转换成相交链表呢？显然可以，为什么？因为我们判断环型链表时，是不是只要快慢指针相遇就是有环，那我们要是在这个相遇的这个节点断开是不是就是两个链表找相交节点，如下图所示：

但我说别这样做，前面我们可以看到光找相交节点工作量就比较大，何况我们还需要处理环呢，太繁琐，讨人烦，我们换一种方法，来点小学生的应用题，这不就是你追我赶的题嘛，来两个小方程不就解决了嘛，何必费那么大力气，我们假设slow走了L+X，那么fast是不是就走了2*(L+X)，我们假设fast在人生道路上等待心上人等上了N圈，即N*C，是不是还有在slow身后走的X那段距离（众里寻他千百度，那人却在灯火阑珊处），那是不是就是2*(L+X)=L+X+N*C，好整理一下就是L=N*C-X，诶发现了什么吗？（强调一遍，此时在fast与slow相遇处哦）是不是就是在相遇的这个点fast你随便走吧一定是走了N*C-X与头节点走了L相遇，那这次相遇就是环的入口节点（fast找到slow不容易啊，是不是回忆了一下这些年的心酸，走到当初那个岔路口思绪万千）。如下图所示：

在第二道环形题的基础上，我们只需让fast和head动起来即可，直至它们相遇，因为它们一定相遇💕。所以实现代码如下：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head , *slow = head;
    while(fast && fast->next)//fast和fast->next不能为NULL，因为fast要走两步
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)//遇到就是有环
        {
            while(head != fast)
            {
                head = head->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL; //走到这就是fast或者fast->next为NULL说明遍历了整个链表因此也就没环
}

总结：本篇博客介绍了三道题，这三道题不约而同的有相似的部分，无论是相交链表，亦或是环形链表，这样新的结构，可以扩展我们的知识面，相信再以后面对不一样的题型时，我们仍然可以迎刃有余，希望大家都有所收获，相信本篇博客的学习我们受益匪浅！💯 

🌻数据结构与算法专栏🌻

🏋不是每一粒种子都能开花，但播下种子就比荒芜的旷野强百倍🏋