[C/C++]数据结构 深入挖掘环形链表问题
前言
在上一篇文章中讲述了如何判断链表是否带环,在观看本片文章时建议先了解一下这篇文章的内容[C/C++]数据结构 链表OJ题:环形链表。本篇文章我们将讲述关于环形链表的几种不同的情况如下,同时我们要解决另一个环形链表问题----找到入环点
- slow一次走一步fast一次走两步一定会相遇吗?
- slow一次走一步fast一次走三部一定会相遇吗?
- 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就又不会相遇,同理这种情况无论第几次追逐两指针都不会相遇
总结:
- 如果N为偶数,两指针在第一轮追逐就会相遇
- 如果N为奇数,c为奇数,第一轮两指针会错过,但是在第二轮会相遇
- 如果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;
}