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

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

示例 1：

img

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

示例 2：

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

示例 3：

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

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

解题思路：快慢指针

  1. 快指针先移动n步
  2. 然后快慢指针一起移动，当快指针移动到链表末尾时，慢指针正好移动到我们要删除的节点
  3. 使用pre来标记要删除节点的前一个位置，来保证删除操作节点不丢失

思路和剑指Offer22 链表中倒数第K个结点一致，就是多了个删除操作。

代码实现：

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
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pre = dummy;
    
    ListNode fast = head;
    
    ListNode cur = head;
    
    while(n > 0 && fast != null){
        n--;
        fast = fast.next;
    }
    
    if(n > 0){
        return null;
    }
    
    while(fast!=null){
        fast = fast.next;
        pre = cur;
        cur = cur.next;
    }
    pre.next = cur.next;
    return dummy.next;
}