目录

题目描述

题解1

题解二：快慢指针

题解三：递归

---

题目描述

示例：

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

输入：head = [1], n = 1
输出：[]

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

题解1

遍历链表，计算链表结点个数count，要删除倒数第k个节点，只需要两个指针分别移动到目标，就可以执行删除操作。

很简单的思路，就不用代码演示了 

题解二：快慢指针

思路跟 "返回链表倒数第k个节点" 差不多。

有兴趣可以看一看：力扣.返回倒数第k个节点

定义两个指针p1、p2指向头节点，共N个节点想找倒数第k个。

1 ：p2先走k步，停下，此时p2到达正数第（k + 1）个，剩余N - （k + 1）个节点，

2：p1 和 此时的p2一起走，p2到达尾，p1到达正数第（N - k + 1）个，即倒数第k个

3：返回此时的p1

不一样的是，返回指定节点的循环终止条件为：fast != null，而我们要删除节点，所以要找到指定节点的前一个节点，所以终止条件为：fast.next != null

class Solution {
    int count = 0;
    public ListNode removeNthFromEnd(ListNode head, int k) {
        
        if (head == null) {
            return head;
        }
        ListNode p2 = head;
        ListNode p1 = head;
        for (int i = 0; i < k; i ++) {
            p2 = p2.next;
        } 

        // 如果p2==null，说明k和链表长度相同，此时要删除的就是头节点
        if (p2 == null) return head.next;

        while (p2.next != null) {
            p2 = p2.next;
            p1 = p1.next;
        }

        // 执行删除操作
        p1.next = p1.next.next;
        return head;
    }
}

 特殊情况：要删除的是头节点，即 k == count

这种情况下，在第一步，p2会直接运动到null，所以判断一下 p2是不是为空，为空就返回head.next就可以了。

题解三：递归

思路跟这个很像：

力扣：链表中倒数第k个节点

class Solution {
    // int count = 0;
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 如果遇到尾节点，终止递归
        if (head == null) {
            return head;
        }
        
        // 一直往里面递，(p一直都是null)
        ListNode p = getKthFromEnd(head.next,k);
 
        if (++count == k) {//如果到达目标节点，则返回它的下一个节点
            return head.next;
        }else {
            return p; // 没找到就继续往回归
        }
    }
}