一、题目

给定单向链表的一个头指针和节点指针，定义一个函数在O(1)时间删除该节点。

二、解题思路

Notzuonotdied的思路

定义传递进来的结点为root: LinkNode, targetNode: LinkNode?，返回类型允许为空。
root默认不能为空(kotlin类型不带问号，表示禁止为空)。
判断targetNode是否为空。为空直接返回root，否则往下执行。
判断targetNode是否是头结点。如果是，就返回root的下一个结点。如果下一个结点为空，直接返回null。
判断targetNode是否为尾节点。如果是，直接循环到倒数第二个结点，将结点的next属性设为null，并返回root。
targetNode位于链表中间。直接将targetNode的value设置为下下个结点的值，targetNode的next设置为下下个node。

Kotlin实现

fun main(args: Array<String>) {
    var node = create(start = 0, end = 10)
    print("初始化输出 -> ")
    print(node)
    print("删除后输出 -> ")
    deleteNode(node, getNode(value = 6, root = node))
    print(node)
    // 边界测试
    print("边界测试0 -> ")
    node = create(start = 0, end = 10)
    print(deleteNode(node, targetNode = node))
    print("边界测试1 -> ")
    node = create(start = 0, end = 10)
    print(deleteNode(node, targetNode = getNode(1, node)))
    print("末尾node测试 -> ")
    node = create(start = 0, end = 10)
    print(deleteNode(node, targetNode = getNode(10, node)))
}

/**
 * 创建链表
 *
 * @param start 起始结点
 * @param end 结束结点
 * @return 返回头结点
 * */
fun create(start: Int, end: Int): LinkNode {
    val root = LinkNode(233, null)
    var temp = root
    for (i in start..end) {
        val node = LinkNode(i, next = null)
        temp.next = node
        temp = node
    }
    return root
}

/**
 * 获取结点
 *
 * @param value 结点的值
 * @param root 头结点
 * @return 返回目标结点
 * */
fun getNode(value: Int, root: LinkNode?): LinkNode? {
    var temp = root
    while (temp != null) {
        if (temp.value == value) return temp
        temp = temp.next!!
    }
    return temp
}

/**
 * 输出链表
 *
 * @param root 头结点
 * */
fun print(root: LinkNode?) {
    var temp = root
    while (temp != null) {
        print(temp.value)
        print(" ")
        temp = temp.next
    }
    println()
}

class LinkNode(var value: Int, var next: LinkNode?)

/**
 * 删除结点
 *
 * @param root 头结点
 * @param targetNode 目标结点
 * @return 头结点
 * */
fun deleteNode(root: LinkNode, targetNode: LinkNode?): LinkNode? {
    // 如果为空，直接返回根结点
    if (targetNode == null) return root

    // 如果是头结点
    if (root == targetNode) return root.next

    // 如果是最后一个结点
    if (targetNode.next == null) {
        var tempRoot = root
        while (tempRoot.next != targetNode) {
            tempRoot = tempRoot.next!!
        }
        tempRoot.next = null
    } else {
        targetNode.value = targetNode.next!!.value
        targetNode.next = targetNode.next!!.next
    }

    return root
}

输出结果

初始化输出 -> 233 0 1 2 3 4 5 6 7 8 9 10 
删除后输出 -> 233 0 1 2 3 4 5 7 8 9 10 
边界测试0 -> 0 1 2 3 4 5 6 7 8 9 10 
边界测试1 -> 233 0 2 3 4 5 6 7 8 9 10 
末尾node测试 -> 233 0 1 2 3 4 5 6 7 8 9

O(1)删除链表结点

一、题目

二、解题思路

Notzuonotdied的思路

Kotlin实现

输出结果