链表中环的检测

1. 怎么检测一个单向链表中是否有环

同样借助于快慢指针，思路如下：

1. 定义 fast、slow 两个指针同时指向链表头部；
2. 开始遍历链表，slow 每次移动步数为 1 ，fast 每次移动步数为 2 ；
3. 如果链表中没有环，则 fast 指针必然会移动到链表尾部，最后会指向 null；
4. 如果链表中有环，则在移动的过程中，fast 与 slow 两个指针必然会在某个节点相遇；

想象成环形运动场跑步，跑得慢的人与跑得快的人同时出发，跑得快的人必然会超过跑得慢的人，并且会再次追上。

代码如下（kotlin编写）：

/**
 * 链表数据结构
 */
class Node constructor(val data: Char) {
    var next: Node? = null

    override fun toString(): String {
        val sb = StringBuilder()
        sb.append(data)
        var tmp: Node? = next
        while (tmp != null) {
            sb.append(tmp.data)
            tmp = tmp.next
        }
        return sb.toString()
    }
}

/**
 * 检测是否有环
 */
fun detectCircle(head: Node?): Boolean {
    head ?: return false
    head?.next ?: return false

    var fast = head
    var slow = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast?.next?.next
        if (fast == slow) {
            return true
        }
    }
    return false
}

//测试代码
fun main() {
    var node1 = Node('1')
    var node2 = Node('2')
    var node3 = Node('3')
    var node4 = Node('4')
    var node5 = Node('5')
    var node6 = Node('6')
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node6
    node6.next = node3

    println(detectCircle(node1))
}

2. 找到链表环的入口节点

image.png

图中入口节点为 3 ，由于 x 与 z 相等，所以我们用 2 个指针，一个从链表头部 1，一个从相遇点 6， 同时开始同速度移动，最后它俩的相遇点就是环的入口节点。

这个图比较简单，只是方便理解。实际上，x 可能会很大，而链表内的环长度比较小，并不能照图中来推论，下面是具体推论：

首先根据图中所示，需要求解 x 的长度？
环长：L = y + z
slow指针移动长度：S = x + y
fast指针移动长度：2S = x + nL + y（fast 是 slow 的 2 倍速度，n 目前未知）
所以： 2(x + y) = x + nL + y
求得：x = nL - y = nL - y - z + z = nL - (y + z) + z = (n - 1)L + z
最终：x = (n - 1)L + z，这里 n >= 1

假设一个指针从链表头部，一个指针从环里的相遇点开始移动，当前者移动到环入口节点时：
当 n = 1 ，从相遇点到环入口节点只需移动 z 次；
当 n = 2 ，从相遇点到环入口节点，需要绕着环走一圈后，再移动 z 次；
以此类推，不管怎么样，这2个指针最终都会在入口处相遇。

代码如下：

fun findCircleEntryNode(head: Node?): Node? {
    head ?: return null
    head?.next ?: return null

    var fast = head
    var slow = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast?.next?.next
        if (fast == slow) {
            break
        }
    }
    //如果有环
    if (fast == slow) {
        if (fast == head)
            return head
        var tmp = head
        while (tmp?.next != null) {
            tmp = tmp?.next
            fast = fast?.next
            if (tmp == fast) {
                return tmp
            }
        }
    }
    return null
}

时间复杂度：O(n)
空间复杂度：O(1)