删除链表倒数第n个节点

给定一个单向链表，要求删除倒数第 n 个节点。

思路如下：

1. 要删除倒数第 n 个节点，其实要先找到倒数第 n + 1 几个节点，即倒数第 n 个节点的前置节点；
2. 考虑使用快慢指针的方式来寻找倒数第 n + 1 个节点；
3. 定义 fast、slow 两个指针同时指向链表头部，先将 fast 指针往后移动 n 步，这样 fast、slow 两个指针之间间隔 n - 1 个节点；
4. 接着同时移动这 2 个指针，直到 fast 指针到底链表尾部，这时候 fast 指针是倒数第 1 个节点，而 slow 指针与 fast 之间间隔 n - 1 个节点，算起来 slow 指针刚好指向的就是倒数第 n + 1 个节点；
5. 通过 slow 指针链表操作删除倒数第 n 个节点；

代码如下（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
}

/**
 * 删除倒数第 n 个节点
 */
fun deleteReciprocalNode(head: Node?, n: Int): Node? {
    head ?: return head
    //n 从 1 开始
    if (n <= 0) return head

    //要删除倒数第 n 个节点，必须找出倒数第 n + 1 个节点
    var fast = head
    var slow = head

    //先将快指针向后移动 n 步
    var step = 0
    while (step < n) {
        if (fast?.next != null) {
            step++
            fast = fast?.next
        } else {
            break
        }
    }
    //n 超出了链表的范围
    if (step < n - 1) {
        return head
    }
    //要删除的刚好是 head 头节点
    if (step == n - 1) {
        return head?.next
    }
    //同时移动快指针、慢指针，直到快指针到达链表尾部
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast?.next
    }

    //slow 指针指向的刚好就是倒数第 n + 1个节点，删除倒数第 n 个节点
    var tmp = slow?.next
    slow?.next = tmp?.next
    //需要注意被删除节点的内存释放
    tmp?.next = null

    return head
}

fun main() {
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 0))
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 1))
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 2))
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 3))
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 4))
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 5))
    println(deleteReciprocalNode(toLinkedListStr("abcde"), 6))
}

执行结果：

abcde
abcd
abce
abde
acde
bcde
abcde

时间复杂度：O(n)
控件复杂度：O(1)