单链表找环
数据结构考试题
上课没听导致做不出来。。
快慢指针
设指针 slow,fast 的步长分别为 和 ,且都从头节点出发。
结论1:最终两个指针会在环中相遇,且此时慢指针 slow 还未走完环一圈。
证明:
设整个链表的线性部分长度为 ,环的长度为 ,相遇时 slow 指针在环中走了 步。
假设
则 slow 指针总共走了 步,由于 fast 指针速度为 slow 指针2倍,所以 fast 指针走了 步。
则 slow 指针在环中走了 步,fast 指针在环中走了 步。
若 ,则
由常识可知若两指针经过路程差大于环的长度,则两指针必定已经相遇过。
与假设矛盾,故 。
那么现在已知两指针会在环中相遇,且此时慢指针还未走完一圈。
问题只剩下怎么确定环的入口。
设现在两指针相遇位置为 ,则我们把 slow 指针指向链表头节点,fast 指针保持在 点,但设置 fast 指针步长为 ,即现在两指针速度相等。
结论2:两指针同时出发,当两个指针相遇时,相遇点即环的入口。
证明:
由结论1的证明可知,从环的起点走 步到达 点。
同样,由结论1的证明过程已知 当两指针相遇时
由常识得当两指针第一次相遇时 fast 恰好超过 slow 一圈,即 。
则
slow 指针走到环的入口处需要 步,故当 slow 指针在环的入口处时,fast 指针距离环的入口 步(fast 指针步长已经被调为1),
由式①可知此时 fast 也绕完了一圈,到达环的入口。两环在环的入口处相遇。
代码实现(返回环的入口指针):
1 | Node *detectCycle(Node *head) { |
至于要环的长度,就新建一个tmp指向入口,一直往下走,再次走到入口返回计数器即可。
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment