Kotlin实现链表正向/反向指定位置节点删除功能问题

实现思路 #

• 首先校验输入的position合法性，小于1直接返回原链表
• 遍历一次链表获取总长度，将反向删除的位置转换为正向位置，复用同一套删除逻辑
• 单独处理删除头节点的场景，直接返回原节点的下一个节点作为新头
• 其他场景定位到待删除节点的前置节点，修改指针跳过待删除节点即可完成操作

完整实现代码 #

首先是基础数据类和修正后的测试代码：

data class Node(
    var value: Int,
    var next: Node? = null
)

fun main() {
    // 测试反向删除第4个节点（原链表：1->2->3->4）
    val list1 = Node(1, Node(2, Node(3, Node(4))))
    val res1 = deleteMyNode(list1, 4, true)
    printNode(res1) // 输出：2->3->4

    // 测试正向删除第4个节点（原链表：1->2->3->4）
    val list2 = Node(1, Node(2, Node(3, Node(4))))
    val res2 = deleteMyNode(list2, 4, false)
    printNode(res2) // 输出：1->2->3
}

// 辅助工具：打印链表结构
fun printNode(node: Node?) {
    val builder = StringBuilder()
    var current: Node? = node
    while (current != null) {
        builder.append(current.value)
        if (current.next != null) builder.append("->")
        current = current.next
    }
    println(builder.toString())
}

核心deleteMyNode函数实现：

// 若需支持删除后链表为空的场景，可将返回值类型改为 Node?
private fun deleteMyNode(node: Node, position: Int, reverse: Boolean): Node {
    // 非法位置直接返回原链表
    if (position < 1) return node

    // 计算链表总长度
    var length = 0
    var current: Node? = node
    while (current != null) {
        length++
        current = current.next
    }

    // 位置超出链表长度，返回原链表
    if (position > length) return node

    // 转换为正向待删除位置
    val targetPosition = if (reverse) length - position + 1 else position

    // 处理删除头节点的场景
    if (targetPosition == 1) {
        return node.next ?: node
    }

    // 定位到待删除节点的前置节点
    var pre: Node? = node
    repeat(targetPosition - 2) {
        pre = pre?.next
    }

    // 修改指针完成删除
    pre?.next = pre?.next?.next

    return node
}

注意事项 #

原测试代码存在多余右括号的语法错误，上述实现已修正。如果需要兼容删除后链表为空的场景，建议将函数返回值类型修改为Node?，避免空指针异常。

内容的提问来源于stack exchange，提问作者sunny kumar