[NC]53. 删除链表的倒数第n个节点

🚩传送门：牛客题目

题目

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

示例 1：

输入：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 个结点，然后落后的慢指针和快指针一起跑

  - 慢指针 **pre **正常指向的是删除结点的前一个结点
  - 当 **cur **跑完 **n** 步变成 `null` ，慢指针 **pre **指向的就是要删除的 **head** 结点

图：快指针先跑 n 步，指向第 n+1 个结点

图：当 cur 跑完 n 步变成 null ，慢指针 pre 指向的就是要删除的 head 结点

图：正常慢指针 pre 指向的是要删除结点的前一个结点

我的代码

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur=head;
        ListNode pre=head;
        //1.快指针先跑 n 个
        for(int i=0;i<n;i++){
            cur=cur.next;
        }
        //2.如果 cur 为空说明head就是要删除的结点
        if(cur==null){
            return head.next;
        }
        //3.如果 cur.next==null , pre就是要删除的前一个结点
        while(cur.next!=null){
            cur=cur.next;
            pre=pre.next;
        }
        //4.删除pre的下一个结点
        pre.next=pre.next.next;
        return head;
    }
}