删除单链表倒数第k个结点

思路：

1. 定义两个指针，分别指向链表的头节点，同时将其中一个指针向后移动k-1个节点。

2. 然后同时移动两个指针，直到后面的指针到达链表末尾。

3. 此时前面的指针指向的就是倒数第k个节点的前一个节点，将其指向下下一个节点即可。

4. 注意特殊情况，比如k大于链表长度或k等于1的情况。

代码实现：

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        p1 = p2 = dummy  # 定义两个指针，都指向dummy节点
        for i in range(n):  # p2指针向后移动n-1个节点
            p2 = p2.next
        while p2.next:  # 同时移动两个指针，直到p2到达链表末尾
            p1 = p1.next
            p2 = p2.next
        p1.next = p1.next.next  # 删除倒数第n个节点
        return dummy.next

时间复杂度：$O(n)$，其中n为链表长度。

空间复杂度：$O(1)$，只需要常数级别的额外空间。