一、题目

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

二、解题思路

Notzuonotdied的解题思路

题目说的是输出倒数的第K个结点，所以我们可以通过维护两个索引[指针]head和last。
假设链表的头结点为root，head和last都指向root。
注意：head和last相差$K - 1$个结点。
head先走K个结点，如果链表总的结点数小于K个结点，就直接返回null；如果链表总的结点数大于K个结点，就遍历K个结点：
- 之后，head和last索引一起遍历结点，直到head为null。
返回last所在的结点的值。

kotlin实现

fun main(args: Array<String>) {
    val length = 16
    val root = initLinkList(length)
    print(root)
    // index比链表长度小
    var postIndex = 5
    println("倒数第${postIndex}个的值为：${printLastKthNode(root, postIndex)?.value}")
    // index比链表长度大
    postIndex = length + 1
    println("倒数第${postIndex}个的值为：${printLastKthNode(root, postIndex)?.value}")

    // 测试边界
    println("××××××测试一个结点的情况××××××")
    val root1 = LinkNode(0, null)
    // 一个元素
    println("倒数第${1}个的值为：${printLastKthNode(root1, 1)?.value}")
    println("倒数第${2}个的值为：${printLastKthNode(root1, 2)?.value}")
    // 零个元素
    println("××××××测试零个结点的情况××××××")
    println("倒数第${1}个的值为：${printLastKthNode(null, 1)?.value}")
    println("倒数第${2}个的值为：${printLastKthNode(null, 2)?.value}")

}

/**
 * 初始化单链表
 *
 * @return 返回单链表
 * */
fun initLinkList(length: Int): LinkNode? {
    val root = LinkNode(0, null)
    var temp: LinkNode = root
    for (i in 1..(length - 1)) {
        temp.next = LinkNode(i, null)
        temp = temp.next!!
    }
    return root
}

/**
 * 输出倒数第K个结点
 *
 * @param root 头结点
 * @param k 倒数第几个结点的索引值
 * @return 返回倒数第K个结点
 * */
fun printLastKthNode(root: LinkNode?, k: Int): LinkNode? {
    // 如果k的值等于0，就直接抛出异常
    if (k == 0) throw Exception("请输入大于0的数字k")
    // 如果头结点为空，就直接返回root
    if (root == null) return root

    // 初始化遍历的head索引
    var head = root
    // head先遍历k个结点，保持head和
    for (i in 0..(k - 1)) {
        // 不为空就往下走，为空就直接返回null
        if (head != null) {
            head = head.next
        } else return null
    }
    // 遍历直到head为null，找到倒数第k个结点
    var last = root
    while (head != null) {
        head = head.next
        last = last?.next
    }

    return last
}

输出结果

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
倒数第5个的值为：11
倒数第17个的值为：null
××××××测试一个结点的情况××××××
倒数第1个的值为：0
倒数第2个的值为：null
××××××测试零个结点的情况××××××
倒数第1个的值为：null
倒数第2个的值为：null

输出单链表倒数第K个结点

一、题目

二、解题思路

Notzuonotdied的解题思路

kotlin实现

输出结果