写点什么

判断链表是否有环

用户头像
Kenn
关注
发布于: 2020 年 04 月 28 日

判断单链表是否有环,以及环的长度和环开始的地方是常见的面试题,如leetcode上的判断是否有环(https://leetcode.com/problems/linked-list-cycle/)和给出环的起点(https://leetcode.com/problems/linked-list-cycle-ii/),基本上这种问题的解决思路就是快慢指针,这里我们介绍下Brent's Cycle Detection Algorithm, 思路其实就是快慢指针,但是略有不同。



快慢指针



快慢指针的思路其实就是,快指针每次往前移动两次而慢指针每次移动一次,那么如果这个单链表存在环路的话,迟早快指针会和慢指针相遇,否则就不存在环路。

func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head.Next
for slow != fast {
if fast == nil || fast.Next == nil {
return false
}
slow = slow.Next
fast = fast.Next.Next
}
return true
}



Brent's Cycle Detection Algorithm

Brent算法虽然也是用快慢两个指针来检测环,但是区别是快指针每次移动2^N次之后才去移动慢指针,比如,一开始快指针移动2步,然后去更新慢指针,然后4步、8步直到找到环路或者发现并不存在环路。Brent's算法有两个优势,一个是算法常数上来说会快于传统的快慢指针(两者都是O(N)),另外一个是,当要求给出环路的长度的时候,Brent's的算法在检测到环路的同时,就已经得到环路的长度了,不需要额外的计算,相当于了一个side effect。

func hasCycle(head ListNode) bool {
if head == nil || head.Next == nil {
return false
}
fast, slow := head, head
stepstaken, steplimit := 0, 2
for {
if fast == nil {
return false
}
fast = fast.Next
stepstaken++
if fast == slow {
break
}
if stepstaken == steplimit {
stepstaken = 0
step_limit = 2
slow = fast
}
}
return true
}

当算法结束的时候,steps_taken就是环的长度,这里面的逻辑是这样的,我们需要快速把slow和fast两个指针迭代进入环,只要slow和fast两个指针进入环中,此时只要移动快指针N步,当N大于等于环路的长度的时候,那么自然两个指针会相遇,记录快指针移动了多少步的变量steps_taken就是环路的长度了



环路的起点

如果我们同时需要直到环路从哪个node开始,还需要一个些额外的逻辑来处理。

fast, slow = head, head
for stepstaken > 0 {
fast = fast.Next
stepstaken--
}
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return slow

上面这段代码可以帮助我们找到作为环起点的node,这里初看可能有点不是很直观,但是内在的逻辑很简单。我们假设整个单链表的长度(节点数)为N, 环的长度为L,环的起点的index为I 那么第一个for循环跑完之后,fast指针位于L的位置, 由于N = L + I,那么快指针再走I步就到了loop的起点,此时慢指针处于0的位置,慢指针走I步也到了loop的起点, 所以在第二个loop里,我们让快慢指针同时往前走,如果他们相遇,就代表他们同步到达了loop的起点。



Reference

  1. http://www.siafoo.net/algorithm/11



发布于: 2020 年 04 月 28 日阅读数: 63
用户头像

Kenn

关注

忘记密码 记住我 2018.03.09 加入

Démon de Laplace

评论

发布
暂无评论
判断链表是否有环