C语言之带环链表

07-21 1170阅读

带环链表是数据结构链表中的一个经典问题,这里我们研究该问题分为两个方向:链表是否带环、返回链表的入环节点。

下面我们通过两个题目来分析带环链表:

1.判断链表是否带环

141. 环形链表 - 力扣(LeetCode)

C语言之带环链表

 那么我们要怎么判断一个链表是否带环呢?

这里我们直接给出答案:借助快慢指针来判断链表是否带环。

我们创建两个指针变量slow和fast,slow一次走一步,fast一次走两步,如果链表带环,那么fast就会先进入环,当slow也进入环之后,它们就开始了追击,因为fast走得比slow快,所以fast和slow一定会相遇,如果fast和slow相遇了,就证明了该链表是带环链表;如果fast走到了NULL,那么就说明该链表是不带环的。

分析图如下:C语言之带环链表

 这个逻辑还是很简单的,该操作的代码也很简单,这里直接给出:

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;    
}

到这里了就有问题了,那这样子写的原理是什么呢?我们借助图来解释一下:C语言之带环链表

到这里,问题就解决了么?其实还没有,fast走2步可以,那么fast走3步,4步,n步可不可以呢? 

下面我们来研究一下fast走3步的情况:

1.1fast走3步

我们借助图来分析:C语言之带环链表

我们看到,如果C-1是奇数的话,他就会陷入循环中,每一次都追不上,且每一次的距离都是C-1。那么fast走4步和走n步都是同样的分析道理,大家感兴趣的话可以自己推一下。 

我们现在就要问了,fast走三步真的追不上么?

1.2fast走三步到底追不追得上?

我们在上面说当N是奇数且C-1是奇数的时候就追不上,那么事实是这样的么?我们继续分析一下。我们假设进环前的路程为L,所以slow走的路程就是L,fast走的路程是L+x*C+N。x表示fast在环中走的圈数,因为在slow进环之前,fast可能已经在环中走了好几圈了。N表示slow刚入环时,fast和slow的距离。

然后又因为fast一次走三步,slow一次走一步,所以fast走的路程是slow路程的三倍。所以有等式:3L = L+x*C+N。化简得:2L = x*C+N。C语言之带环链表

综上所述,当fast一次走三步时,不管slow刚进入环时,fast和slow的距离N是奇数还是偶数,都会追上。偶数会在第一次追击就追上;奇数则会在第二次追击追上。 

2.返回带环链表的第一个入环节点 

142. 环形链表 II - 力扣(LeetCode)

C语言之带环链表

我们在先前判断了一个链表是否带环,我们现在要返回该带环链表的入环节点。 C语言之带环链表

如上图所示,我们要返回的入环节点就是节点2。 

其实非常的简单,我们现在已经知道,不管fast一次走多少步,fast和slow总会相遇。我们定义连个指针head和meet,分别从链表的第一个节点和fast、slow相遇的节点开始遍历,等到head和meet相等的时候,此时两个指针指向的就是环入口的节点。

这是什么原理呢?C语言之带环链表

fast和slow的路程为什么是这样的呢?

我们想,slow可不可能在环中走过超过一圈呢?当然不可能了。因为fast走的是slow的2倍,如果slow走了一圈,那么fast就走了两圈,它们肯定就已经相遇了。所以slow的路程是L+N。

而因为fast走得比较快,所以当slow入环时,fast已经在环中转了好几圈了。那么我们想一下,fast可不可能一圈都没转完?不可能,因为如果一圈都没走完,那么fast走的路程还没有slow的多,因为slow路程的2倍才是fast的路程。

所以根据上面的公式,以及fast一次走二步,slow一次走一步,我们可以得出一个等式:

2(L+N)= L+x*C+N。化简得:L+N = x*C ,继续化简得:L = x*C-N,我们将该式带入图中:C语言之带环链表

 其上,就是我的证明过程。head和meet同时遍历链表,当相等的时候,它们指向的都是入环的第一个节点。下面给出代码:

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            while(head != fast)
            {
                head = head->next;
                fast = fast->next;
            }
            return head;
        }
    }
    return NULL;
}
VPS购买请点击我

文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。

目录[+]