链表-删除链表倒数第N个节点

发表于 分类于

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

示例 1：

img

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

输入：head = [1], n = 1
输出：[]
示例 3：

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

这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用，可以用我们实现的 findFromEnd 来操作。

不过注意我们又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。

但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 删除单链表倒数第N个节点
 * @param head
 * @param n
 * @return
 */
public static ListNode removeNthFromEnd(ListNode head, int n) {
    //虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    //删除倒数第n个，要先扎到找到倒数第n+1个节点
    ListNode x = findFromEnd(dummy.next, n + 1);
    //删掉倒数第n个节点
    x.next = x.next.next;
    return dummy.next;
}

// 返回链表的倒数第 k 个节点
public static ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for(int i=0;i<k;i++){
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1!=null){
        p1 = p1.next;
        p2 = p2.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}