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

原题链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

1.思路一：先反转，再删除，再反转

这样的时间复杂度无疑是 $O(3n)$ ，最坏的情况下要遍历 3 次。

//思路一：先反转，再删除
public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null || head.next == null) { //如果链表为空，直接返回
        return null;
    }
    ListNode newHead = reverseList(head);
    //反转完毕，下面开始搜索n并删除
    ListNode virHead = new ListNode(0, newHead); //创建虚拟头节点
    ListNode temp = virHead; //创建辅助节点
    int counter = n; //计数器
    temp = virHead; //辅助节点指向反转后的虚拟头节点
    while (counter > 1) { //定位到要删除节点的前一个节点
        temp = temp.next; //辅助节点后移一位
        counter--;
    }
    //定位完毕，开始删除
    temp.next = temp.next.next; //删除节点
    return reverseList(virHead.next); //再反转回开始顺序的链表，返回
}

//把反转链表的功能抽象出来
private static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode pre = null;
    ListNode temp = null;
    while (head != null) { //双指针法反转链表
        temp = head.next;
        head.next = pre;
        pre = head; // pre后移一位
        head = temp; //head后移一位
    }
    return pre;
}
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
34
35

2.思路二：快慢指针，快针先跑n+1，再快慢同时移动

这个方法我学习之后也是叹为观止。核心思想是先让快指针 fast 先移动 n+1 步，慢指针 slow 不动。然后再让快慢指针同时往后移动，直到快指针 fast 到达链表末尾为止。此时 slow 就定位到要删除节点的上一个节点了，接下来只要 slow.next = slow.next.next 就完成了倒数第 n 个节点的删除。

这样只遍历一遍就可以完成，时间复杂度为 $O(n)$ 。以下是步骤详解：

• 创建虚拟头节点 virHead ，创建快慢指针并初始化，都指向虚拟头节点 virHead 。

  

• 慢指针 slow 先不动，快指针 fast 先移动 n + 1 步。之所以是 n + 1 ，是为了让慢指针 slow 定位到要删除节点的上一个节点。

  

• 快慢指针同时移动，直到快指针 fast 指向 null 为止。此时慢指针 slow 定位到要删除节点的上一个节点。

  

• 接下来只要 slow.next = slow.next.next 就完成了倒数第 n 个节点的删除。

  

//思路二：快慢指针，快针先跑n，再快慢同时移动
public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null || head.next == null) { //如果链表为空或只有一个节点，直接返回空链表
        return null;
    }
    ListNode virHead = new ListNode(0, head); //创建虚拟头节点
    ListNode fast = virHead; //快指针
    ListNode slow = virHead; //慢指针
    while (fast != null) {
        if (n > -1) { //这里是-1是为了让slow定位到要删除节点的上一个节点
            fast = fast.next; //快指针先移动n步
            n--;
        } else { //快慢指针同时后移
            fast = fast.next;
            slow = slow.next;
        }
    }
    slow.next = slow.next.next; //删除倒数第n个节点
    return virHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20