数据结构之环形链表的有关解法

用户11289931

发布于 2024-09-24 16:33:45

930

发布于 2024-09-24 16:33:45

文章被收录于专栏：学习

算法是锻炼编程能力的重要路径。那么今天我来分享两道有关环形链表的解法：

快慢指针，即慢指针⼀次⾛⼀步，快指针⼀次⾛两步，两个指针从链表起始位置开始运⾏，如果链表带环则⼀定会在环中相遇，否则快指针率先⾛到链表的未尾

环形链表1

题源：

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

*环形链表：链表的尾节点指向的next不为空。

思路：

运用快慢指针的移动来判断是否为环形链表（若相遇则说明是环形）

如下图：那么为什么快慢指针会相遇呢？（下图中快指针一次移动2步，慢指针一次移动1步）

我们假设环的长度为C

slow⼀次⾛⼀步，fast⼀次⾛2步，fast先进环，假设slow也⾛完⼊环前的距离，准备进环，此时fast 和slow之间的距离为N，接下来的追逐过程中，每追击⼀次，他们之间的距离缩⼩1步

追击过程中fast和slow之间的距离变化：

因此，在带环链表中慢指针⾛⼀步，快指针⾛两步最终⼀定会相遇。

那么，当快指针⼀次⾛3步，⾛4步，...n步，它们还会再相遇吗？

step1:

按照上⾯的分析，慢指针每次⾛⼀步，快指针每次⾛三步，此时快慢指针的最⼤距离为N，接下来的追逐过程中，每追击⼀次，他们之间的距离缩⼩2步

追击过程中fast和slow之间的距离变化：

分析:

1、如果N是偶数，第⼀轮就追上了 2、如果N是奇数，第⼀轮追不上，快追上，错过了，距离变成-1，即C-1，进⼊新的⼀轮追击 a、C-1如果是偶数，那么下⼀轮就追上了 b、C-1如果是奇数，那么就永远都追不上总结⼀下追不上的前提条件：N是奇数，C是偶数

step2：

假设：环的周⻓为C，头结点到slow结点的⻓度为L，slow⾛⼀步，fast⾛三步，当slow指针⼊环后， slow和fast指针在环中开始进⾏追逐，假设此时fast指针已经绕环x周。

在追逐过程中，快慢指针相遇时所⾛的路径⻓度: fast: L+xC+C-N slow：L 由于慢指针⾛⼀步，快指针要⾛三步，因此得出： 3 * 慢指针路程 = 快指针路程 ，即： 3L = L + xC + C − N 2L = (x + 1)C − N 对上述公式继续分析：由于偶数乘以任何数都为偶数，因此2L⼀定为偶数，则可推导出可能得情况：情况1：偶数=偶数-偶数情况2：偶数=奇数-奇数

由step1中（1）得出的结论，如果N是偶数，则第⼀圈快慢指针就相遇了。

由step1中（2）得出的结论，如果N是奇数，则fast指针和slow指针在第⼀轮的时候套圈了，开始进⾏下⼀轮的追逐；当N是奇数，要满⾜以上的公式，则 (x+1)C 必须也要为奇数，即C为奇数，满⾜（2）a中的结论，则快慢指针会相遇因此，step1中的 N是奇数，C是偶数，既然不存在该情况，则快指针⼀次⾛3步最终⼀定也可以相遇。

解法：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
 ListNode* slow,*fast;
 slow = fast = head;
 while(fast && fast->next)
 {
 slow = slow->next;
 int n=3; //fast每次⾛三步
 while(n--)
 {
 if(fast->next)
 fast = fast->next;
 else
 return false;
 }
 if(slow == fast)
 {
 return true;
 }
 }
 return false;
}

环形链表2

题源：

142. 环形链表 II - 力扣（LeetCode）

首先我们来看一个结论，后面会给大家证明：

让⼀个指针从链表起始位置开始遍历链表,同时让⼀个指针从判环时相遇点的位置开始绕环运⾏,两个指针都是每次均⾛⼀步,最终肯定会在⼊⼝点的位置相遇。

思路：

1.找快慢指针在环内的相遇点

2.从头结点和相遇点开始遍历，每次走一步

3.第2步中的最终相遇点即为环的入口点

证明：

说明:

H为链表的起始点，E为环⼊⼝点，M与判环时候相遇点设: 环的⻓度为R，H到E的距离为L，E到M的距离为 X ，则：M到E的距离为 R-X 在判环时,快慢指针相遇时所⾛的路径⻓度: fast: L+X + nR slow：L+X *n为fast在环内走过的圈数

注意:

1.当慢指针进⼊环时，快指针可能已经在环中绕了n圈了，n⾄少为1

因为：快指针先进环⾛到M的位置,，最后⼜在M的位置与慢指针相遇

2.慢指针进环之后，快指针肯定会在慢指针⾛⼀圈之内追上慢指针

因为：慢指针进环后,快慢指针之间的距离最多就是环的⻓度,⽽两个指针在移动时,每次它们⾄今的距离都缩减⼀步，因此在慢指针移动⼀圈之前快，指针肯定是可以追上慢指针的，⽽快指针速度是慢指针的两倍，因此有如下关系是：

2 * (L+X)=L+X+nR L+X=nR L=nR-X L = (n-1)R+(R-X)

(n为1,2,3,4......，n的⼤⼩取决于环的⼤⼩，环越⼩n越⼤)

极端情况下，假设n=1，此时： L=R-X 。即：⼀个指针从链表起始位置运⾏，⼀个指针从相遇点位置绕环，每次都⾛⼀步，两个指针最终会在⼊⼝点的位置相遇。

如图：（L=R-X即为我们要证明的式子）

解法：

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;
        ListNode*pcur=head;
        if(slow==fast)
        {
            //相遇即链表一定带环
            while(pcur!=slow)
            {
                pcur=pcur->next;
                slow=slow->next;
            }
            return pcur;
        }
    }
    //链表不带环
    return NULL;
}