【数据结构】_链表经典算法OJ：链表判环问题

目录

1. 题目1：环形链表判环是否存在

1.1 题目链接及描述

1.2 解题思路

1.3 程序

2. 关于快慢指针的追击问题

2.1 试分析快指针步长为2的可行性？

2.2 试分析快指针步长为3的可行性？

3. 题目2：环形链表判环是否存在并返回入环首结点

3.1 题目链接及描述

3.2 解题思路

3.3 程序

3.3.1 思路1解法

3.3.2 思路2解法

1. 题目1：环形链表判环是否存在

1.1 题目链接及描述

题目链接：141. 环形链表 - 力扣（LeetCode）

题目描述：

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1.2 解题思路

创建快慢指针fast和slow，令慢指针一次走一步，慢指针一次走两步。

若链表不存在环，则遍历链表时快指针到达尾结点时，其next指针域为NULL；

若链表存在环，则快指针和慢指针进入环后，指针会追击上慢指针；

1.3 程序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* slow=head, *fast=head;
    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

2. 关于快慢指针的追击问题

假设链表存在环，慢指针步长为0。

2.1 试分析快指针步长为2的可行性？

假设slow进环时，slow与fast距离为N，由于快指针步长为2，慢指针步长为1，则fast追击slow时，二者距离依次减1，则N经N-1、N-2、N-3...2、1、0，即快指针追上慢指针。故：

当快指针步长为2时，快指针必然可以追上慢指针。

2.2 试分析快指针步长为3的可行性？

假设slow进环时，slow与fast距离为N，由于快指针步长为3，慢指针步长为1，则fast追击slow时，二者距离依次减2，则N变化为：N-2、N-4、N-6...

（1）当N为偶数时，N经N-2、N-4、N-6...4、2、0，逐次减为0，即快指针追上慢指针；

（2）当N为奇数时，N经N-2、N-4、N-6...5、3、1、-1...即出现快指针越过慢指针，开启新一轮的追击，-1表示快指针与慢指针的距离变为C-1，C为环的长度。

① 当C为奇数，C-1为偶数，则快慢指针距离经C-3、C-5...2、0，此时快指针追上慢指针；

② 当C为偶数，C-1为奇数，则快慢指针距离经C-3、C-5...3、1、-1...，即出现快指针将慢指针套圈，-1表示快指针与慢指针的距离变为C-1，此时快指针永远无法追上慢指针。

由以上不严格推导，可得出结论如下：

当快指针步长为3，慢指针步长为1时，当N为奇数且C为偶数时，快指针永远追不上慢指针。

试分析此种情况存在的可能性：

假设链表非环部分长度为L，环长为C，slow进环时fast与slow的距离为N。

故slow进环前走的距离为L，由于slow进环时fast可能已经在环内转多圈，设转了x圈，则slow进环时fast走的距离为L+x*C+C-N。

又由于fast的步长为slow的三倍，故在一定时间内，fast走的距离也是slow的三倍，有：

3*L=L+x*C+C-N，化简有：2*L=(x+1)*C-N，

对于上文得出的，当N为奇数且C为偶数时快指针永远追不上慢指针的情况，可知(x+1)*C必为偶数，N为奇数，则(x+1)*C-N为奇数。这与等号左=2*L必为偶数，则等号右也必为偶数矛盾。

故这种N为奇数且C为偶数的情况实际上是不存在的。

即：慢指针步长为1，快指针步长为3时，快指针必然可以追上慢指针。

对于快指针n＞3的其他步长也可采用类似方式证明，均可证明无论快指针的步长取≥2的任何正整数，都可以追上慢指针，不存在快指针追不上慢指针的情况。

3. 题目2：环形链表判环是否存在并返回入环首结点

3.1 题目链接及描述

题目链接：142. 环形链表 II - 力扣（LeetCode）

题目描述：

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

3.2 解题思路

思路1：理论证明等长（本题解法）

令快指针步长为2，慢指针步长为1，（避免采用其他步长的套圈问题的讨论）；

一个指针从链表的第一个结点head处开始走，一个指针从快慢指针相遇处meet处开始走；

两个指针再次相遇时的结点就是入环的第一个结点。

理论证明：

快慢指针相遇时，slow走的距离为L+N，fast走的距离为L+N+x*C（x≥1）。

（有可能链表非环部分长度远大于环长，故fast在与slow相遇前可能已经转了若干圈）

由于fast的步长为slow的2倍，故在一定时间内，fast走的距离也是slow的2倍，有：

2*(L+N) = L+N+x*C，化简得L+N=x*C，有L=x*C-N=(x-1)*C+C-N；

故从head处和从meet处开始走的两个指针会相遇在入环的第一个结点处；

思路2：转换为链表相交

求得快慢指针相遇处后，将环从meet处截断，并令meet->next为现无环链表的头结点：

将求入环第一个结点的问题转换为以head和newHead为头的两个链表的第一个相交结点的问题。

关于链表求第一个相交结点的解答，详见下文：

【数据结构】_链表经典算法OJ：相交链表-CSDN博客文章浏览阅读54次。由于需定位到两个链表的尾结点，故循环判断条件应为curNodeX->next而非curNodeX，但当遍历至尾结点时不进入循环，如果将链表长度变量lenX初始值设为0，就会导致链表长度计算少算了尾结点，故而在设定链表长度变量lenX时，将其初始值均设为1；为两个链表分别创建结构体指针curNodeA和curNodeB，用第二个链表的每一个结点依次把第一个链表的所有结点都比一遍，直至交点结点处会相等；注：两个指针不可同时走，若相交结点前两个链表长度不同，则会导致即使相交也被判定为不相交的情况；https://blog.csdn.net/m0_63299495/article/details/145411605

3.3 程序

3.3.1 思路1解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow=head,*fast=head;
    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        // 快慢指针相遇
        if(slow==fast){
            ListNode* meet=slow;
            while(meet != head){
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

3.3.2 思路2解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
// 求两个链表的第一个相交结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* curNodeA=headA,*curNodeB=headB;
    // 分别计算两个链表长度
    int lenA=1,lenB=1;
    while(curNodeA->next){
        curNodeA=curNodeA->next;
        lenA++;
    }
    while(curNodeB->next){
        curNodeB=curNodeB->next;
        lenB++;
    }
    // 两个链表直至遍历到尾结点，指针都不等：两个链表不相等；
    if(curNodeA != curNodeB){
        return NULL;
    }
    // 令长链表的遍历指针先走差值步，再同时遍历，第一个相等就是交点
    int gap=abs(lenA-lenB);
    // 假设法：假设A长B短
    ListNode* longList=headA,*shortList=headB;
    // 若假设错误则修正
    if(lenB>lenA){
        longList=headB;
        shortList=headA;
    }
    while(gap--){
        longList=longList->next;
    }
    while(longList != shortList){
        shortList=shortList->next;
        longList=longList->next;
    }
    return shortList;
}
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow=head,*fast=head;
    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        // 快慢指针相遇
        if(slow==fast){
            ListNode* meet=slow;
            ListNode* newHead=meet->next;
            meet->next=NULL;
            return getIntersectionNode(head,newHead);
        }
    }
    return NULL;
}