求链表的中间节点

给定一个单向链表，怎么找到该链表的中位节点？

可以使用快慢指针，定义 2 个指针变量，慢指针移动步数为 1，快指针移动步数为 2，当快指针移动到链表尾部时，慢指针就恰好指向中位节点了。

代码如下（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 toLinkedListStr(str: String?): Node? {
    if (str.isNullOrEmpty())
        return null
    var head: Node? = null
    var next: Node? = null
    for (ch in str) {
        val node = Node(ch)
        next?.next = node
        next = node
        if (head == null) {
            head = node
            next = node
        }
    }
    return head
}

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

    var fast: Node? = head
    var slow: Node? = head
    while(fast?.next != null) {
        fast = fast?.next?.next
        slow = slow?.next
    }
    //此时 fast 指针如果不为空，则链表长度为奇数个，slow 指针刚好指向链表的正中间节点
    //如果 fast 指针为空，则链表长度为偶数个，slow 指针指向的是链表长度一半的后一个节点
    return slow
}

fun main() {
    val str1 = toLinkedListStr("abcde")
    println("$str1 的中位节点是：${findMiddleNode(str1)?.data}")
    println(findMiddleNode(toLinkedListStr(""))?.data)
    println(findMiddleNode(toLinkedListStr("a"))?.data)
    println(findMiddleNode(toLinkedListStr("ab"))?.data)
    println(findMiddleNode(toLinkedListStr("abc"))?.data)
}

执行结果为：

abcde 的中位节点是：c
null
a
b
b

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