142. 环形链表 II - Kotlin 双指针 提供一个更简洁的公式(2n-2a)-(n-a)

Problem: 142. 环形链表 II

思路

设经过n次循环后slow和fast相遇，则此时

• slow走了步
• fast走了步

设slow在环内走了步，则slow在环外走了步

fast的路径：

• 环外->环内slow走的路径->环内slow未走的路径->环内slow走的路径->与slow相遇

由此我们可知fast走了两遍slow在环内走过的路径，则剩余的部分即环外+环内slow未走过的路径=

在slow那里已经求出了环外的长度为n-a步，即环内slow未走的路径=步，即此时环外的长度和slow未走过的路径长度相等，即head和slow相距环入口点的距离相等

解题方法

已知fast和slow相遇时，slow和head距离入口的距离是相等的，则让另一个指针从head出发，两个指针维持相同的速度，即可在环入口处相遇

复杂度

时间复杂度:

空间复杂度:

Code

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

class Solution {
    fun detectCycle(head: ListNode?): ListNode? {
        if (head?.next == null || head.next?.next == null) {
            return null
        }
        var slow = head.next
        var fast = head.next?.next
        while (slow != fast) {
            slow = slow?.next
            fast = fast?.next?.next
            if (slow == null || fast == null) {
                return null
            }
        }

        var ptr = head
        while (slow != ptr) {
            slow = slow?.next
            ptr = ptr?.next
        }
        return ptr
    }
}