19. 删除链表的倒数第 N 个结点（解法二：双指针算法）

19. 删除链表的倒数第 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个节点，可以先让fast指针移动n步，然后让fast和slow同时向后移动，直到fast指针指向链表最后一个元素，删掉slow所指向的节点就可以了。
思路是这样的，但要注意一些细节。
分为如下几步：
第一步：使用虚拟头结点，这样不用考虑头结点的特殊处理情况。
第二步：定义fast指针和slow指针，初始值为虚拟头结点
第三步：fast首先走n+1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）：
第四步：fast和slow同时移动，直到fast指向末尾
第五步：删除slow指向的下一个节点
复杂度分析
时间复杂度：O(L)O(L)，其中 LL 是链表的长度。
空间复杂度：O(1)O(1)。

package com.codernav.demo.leetcode.linkedlist.removeElements;

import com.codernav.demo.common.ListNode;

/**
 * @title 19. 删除链表的倒数第 N 个结点（双指针）
 * @Description 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * @Author 开发者导航
 * @website https://www.codernav.com
 * @date 2023/3/4
 */
public class Q_19_1 {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        // 双指针
        ListNode head = removeNthFromEnd(node1, 2);
        System.out.println(head);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        //只要快慢指针相差 n个结点即可
        for (int i = 0; i < n; i++) {
            fastIndex = fastIndex.next;
        }

        while (fastIndex.next != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }
}