Linked List Cycle II (Medium) 题目描述 给定一个链表，如果有环路，找出环路的开始点。
data class ListNode(var `
val`
: Int
){
var next
: ListNode
? = null
}
fun detectCycle(head
: ListNode
?): ListNode
? {
if (head
== null) return null
var faster
= head
var lower
= head
do {
lower
= lower
!!.next
faster
= faster
!!.next
if (faster
!= null) {
faster
= faster
.next
}
} while (lower
!= faster
&& lower
!= null && faster
!= null)
if(faster
!= null && lower
!= null) {
faster
= head
while (faster
!= lower
) {
faster
= faster
!!.next
lower
= lower
!!.next
}
return lower
}
return null
}
floyd判圆法，快慢指针， fast为low步速2倍时，如果链表有环路，则fast必会追上low，扣圈。则距离上low的距离为s 则 fast 距离为2s。起点到链表环起点的距离为m，环长为n，相遇位置距离环起点为k 则：s= m+ a* n+k (a为low的跑圈数) 2s= m+ b* n+k (b为fast的跑圈数) s=2s-s=(b-a)n 证明此时fast和low的路径皆为环的整数倍
将其中一个节点放在起点，然后同时向前走m步时，此时从头部走的指针在m位置。而从相遇位置开始走的指针应该在距离起点i*s+m，i为圈长整数倍，则该指针也应该在距离起点为m的位置，即环的起点。 参考：https://blog.csdn.net/xiaoquantouer/article/details/51620657
