19. 删除链表的倒数第 n 个结点

删除链表的倒数第 n 个结点可以通过双指针法来实现。首先定义一个虚拟头结点dummy，然后设置两个指针slow和fast，初始时都指向dummy。接着将fast指针向前移动n+1步，然后slow和fast指针一起向前移动，直到fast指针指向空或者到达链表末尾。此时slow指针所指向的结点就是要删除的倒数第n个结点的前一个结点。

然后，我们可以进行删除操作，将slow指针所指结点的next指针指向下下个结点，从而删除倒数第n个结点。最后返回dummy.next即可得到删除倒数第n个结点后的链表。

但是需要注意的是，当要删除的是头结点时，需要单独处理，可以设置一个哨兵结点来避免头结点的特殊情况。

通过双指针法，可以以O(n)的时间复杂度和O(1)的空间复杂度完成删除链表的倒数第n个结点的操作。这种方法的关键在于利用快慢指针的思想，使得在一次遍历中即可完成删除操作，避免了遍历两次链表或使用额外的空间。

相关问题

19. 删除链表的倒数第 N 个结点

好的，我的回答如下：

可以使用双指针来解决这个问题。首先让一个指针先走 n 步，然后让另一个指针从头开始和第一个指针一起走，直到第一个指针到达链表末尾。此时第二个指针所指向的结点就是要删除的结点的前一个结点，可以通过修改指针的方式来删除该结点。

具体实现可以参考以下代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy
    for i in range(n):
        first = first.next
    while first.next is not None:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

用kotlin解决这个问题：19. 删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1], n = 1 输出：[] 示例 3： 输入：head = [1,2], n = 1 输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz

好的，我可以用 Kotlin 为您编写一个解决该问题的函数，如下所示：

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val dummy = ListNode(0)
    dummy.next = head
    var first: ListNode? = dummy
    var second: ListNode? = dummy

    for (i in 1..n+1) {
        first = first?.next
    }

    while (first != null) {
        first = first.next
        second = second?.next
    }

    second?.next = second?.next?.next
    return dummy.next
}

这个函数使用了双指针的方法，时间复杂度为 O(n)，空间复杂度为 O(1)。您可以将该函数直接复制到 Kotlin 代码中并运行，如下所示：

fun main() {
    val head = ListNode(1)
    head.next = ListNode(2)
    head.next?.next = ListNode(3)
    head.next?.next?.next = ListNode(4)
    head.next?.next?.next?.next = ListNode(5)

    val n = 2

    var current = removeNthFromEnd(head, n)
    while (current != null) {
        print("${current.`val`} ")
        current = current.next
    }
}

您可以将上面的代码复制到 Kotlin 的 REPL 环境中并运行，将会输出 `[1, 2, 3, 5]`。