这是我参与更文挑战的第16天，活动详情查看：更文挑战

前言

力扣第十九题 删除链表的倒数第 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]

一、思路

这一题很直观的想法，先遍历一遍链表然后并记录下链表的总个数，然后再从头开始遍历，找到需要删除的节点删除即可。这个思路放在方案一中，复杂度为O(2N)

那怎么优化呢？

其实想要一遍遍历就找到倒数第N个元素，关键就需要记录倒数第N个元素的位置

那么怎么才能找到这个位置呢？其实可以使用快慢指针，先让快指针走N步，然后快慢指针一起走，等到快指针到底的时候慢指针指向的就是倒数第N个元素。

图解快慢指针

黄色指针表示快指针
绿色指针表示慢指针

如下图红色方块表示倒数第N个元素（tips：此处以倒数第三个元素为例）

先让快指针先走N步，即先走3步的结果如下所示：

后面就是快慢指针一起向下走，最后的结果如下图所示：

不难发现当快指针走到底的时候，慢指针此时正好指向倒数第N个元素的前一个元素。此时就可以让慢指针指向下下个节点，即删除倒数第N个元素

伪代码如下：

ListNode slow;  // 慢指针
slow.next = slow.next.next;
复制代码

二、实现

方案一（计数）

这里的实现代码拿的力扣官方的~（请见谅 tnt）

代码实现

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
复制代码

方案二（快慢指针）

代码实现

tips：初始化时快慢指针均指向链表头即可

   /**
     * 快慢指针
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = head;  // 快指针
        ListNode second = head; // 慢指针
        while (first.next != null) {
            first = first.next;
            if (n <= 0)
                second = second.next;
            n --;
        }
        if (n == 1)
            return second.next;
        second.next = second.next.next;
        return head;
    }
复制代码

测试代码

测试代码如下所示

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
//        ListNode listNode = new ListNode(1, new ListNode(2));
        new Number19().removeNthFromEnd(listNode, 5);
    }
复制代码