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]

提示：

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

解析过程：

1、删除链表中的节点，那么实际上就是让该节点的前一个节点直接指向该节点后一个节点，那么直接定位到前节点，当然要想循环一次一个指针就定位到前节点，好像不能实现，那么一个指针不方便解决问题，此时可以考虑两个快慢指针来解决问题。

2、那么使用两个指针怎么就能一遍找到需要删除的节点呢？稍加思考，就可以知道，如果让两个指针间的距离为n-1的话，那么当快指针到了尾节点，慢指针就到了倒数n + 1节点的位置，也就是需要删除节点的前一个节点，那么这样就能很好的实现需要删除节点指向该节点的后一个节点。

3、但是如果需要删除的是第一个节点，当快指针定位到尾节点时，慢指针与快指针之间的距离最大为n-2，这样强行让两个指针间距离为n-1的话就会溢出，如何解决呢？那我们可以加一个节点来保证不会溢出，显然加在头部是非常方便的。

附上代码：

    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode pre = new ListNode();//建立头指针，以便删除第一个节点数据

        pre.next = head;

        ListNode fast = pre;
        ListNode slow = pre;

        for (int i = 0; i < n; i++) {//移动快指针  直至与慢指针相差 n-1个距离
            fast = fast.next;
        }

        if (fast.next == null) {//可以省略   毕竟慢指针在新增头节点  可以直接删除第一个数
            return pre.next.next;
        }

        while (fast.next != null) {//同时移动双指针   将快指针移至尾部
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;//删除中间节点

        return pre.next;
    }

总结：

快慢指针加头节点真好用。

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

原文：https://www.cnblogs.com/jtStudy/p/14600922.html