题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例1:

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

题目分析

快慢指针，快指针提前走 n 步。
后面再同时走，当快指针到达链表尾部时，慢指针恰好在第 n 个元素前面。
使用虚拟节点做头节点，可以避免很多边界case。

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fake = new ListNode(0);
    fake.next = head;
    ListNode slow = fake, fast = fake;
    while (n > 0 && fast != null) {
        fast = fast.next;
        n--;
    }
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return fake.next;
}

Kotlin

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val fake = ListNode(0)
    fake.next = head
    var slow: ListNode? = fake
    var fast: ListNode? = fake
    var count = n
    while (count > 0 && fast != null) {
        fast = fast.next
        count--
    }
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next
    }
    slow?.next = slow?.next?.next
    return fake.next
}