[C/C++]数据结构 深入挖掘环形链表问题

前言

        在上一篇文章中讲述了如何判断链表是否带环,在观看本片文章时建议先了解一下这篇文章的内容[C/C++]数据结构 链表OJ题:环形链表。本篇文章我们将讲述关于环形链表的几种不同的情况如下,同时我们要解决另一个环形链表问题----找到入环点

1. slow一次走一步fast一次走两步一定会相遇吗?
2. slow一次走一步fast一次走三部一定会相遇吗?
3. slow一次走n步fast一次走m步一定会相遇吗? (m>n>1)

情况分析:

1.slow一次走一步fast一次走两步一定会相遇吗?

        这个问题在上一篇文章中我们也讲过,若slow指针已经入环,每走一步fast与slow之间的距离就会减一,减为0时两指针相遇

2.slow一次走一步fast一次走三部一定会相遇吗?

        假设slow入环时,fast和slow之间距离为N

之后每走一步,fast和slow之间的距离就会减小2,这里就需要讨论N的取值了

• 当N为偶数, 距离变化: N -> N-2 -> N-4.......->2 -> 0 ,两指针距离一次减小2,一定会相遇
• 当N为奇数, 距离变化: N -> N-2 -> N-4.......->1 -> -1

        距离变为-1就说明fast在走三步的时候跳过了slow,又跑到了slow的前面,第一轮追逐没有相遇,此时又要开时第二轮追逐,假设环的周长为c,开始第二轮追逐时fast与slow之间的距离为c-1

此时有需要讨论c的取值

• 当c为奇数,c-1为偶数,两指针一定会相遇
• 当c为偶数,c-1为奇数,slow与fast就又不会相遇,同理这种情况无论第几次追逐两指针都不会相遇

总结:

1. 如果N为偶数,两指针在第一轮追逐就会相遇
2. 如果N为奇数,c为奇数,第一轮两指针会错过,但是在第二轮会相遇
3. 如果N为奇数,为偶数,则两指针永远不会相遇

问题来了: 如果N为奇数,为偶数,则两指针永远不会相遇,但是这个条件成立吗?如何验证

slow入环时:

慢指针走的路程: L

快指针走的路程: n*c - N  (n代表走了n圈)

快指针所走路程为慢指针所走路程的三倍,可得:

3L = L+ n*c - N 即 2L = n*c - N

分析一下这个公式:

2L一定为偶数,n*c也一定为偶数,但是n*c-N一定为奇数,因为在条件N就为奇数,

所以我们推出来的公式是错的,也就是说如果N为奇数,为偶数,则两指针永远不会相遇这个条件不成立,即不会出永远追不上的情况,所以不论什么情况两指针都会在某一轮的追逐中相遇

3.slow一次走n步fast一次走m步一定会相遇吗? (m>n>1)

        这种情况和第二种情况分析过程类似,假设slow入环时,fast和slow之间距离为N,每走一步两者距离减(m-n),当N%(m-n)时,两指针便可相遇,由于这类问题给出实际值时才有意义,所以就不对其过多分析了

---

接下来我们解决最后一个问题:

如何找到链表的如环点?

题目描述:

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

分析:

这个题还是采用快慢指针的方法,slow一次走一步,fast一次走两步

由于fast速度是slow的二倍,所以相遇时,fast所走路程为slow的两倍,即

2*(L+x) = L+n*c+x

化简为: L = n*c - x

由这个公式就可以推出:

一个指针从头开始走,一个指针从相遇点开始走,他们会在入环点相遇

有了这个理论,这个题就可以迎刃而解了,我们先找出相遇点(如何找相遇点在前言所提文章中讲过),在让两指针,一个从头开始走,一个从相遇点开始走,判断哪个点符合这个公式

代码:

 
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow=head;
    struct ListNode *fast=head;
 
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)//找相遇点
       {
           struct ListNode* meet=slow;//相遇点
           while(meet!=head)
           {
               head=head->next;
               meet=meet->next;
           }
                return meet;
       }
    }
    return NULL;
}