剑指 Offer II 021. 删除链表的倒数第 n 个结点

剑指 Offer II 021. 删除链表的倒数第 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

进阶：能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/SLwz0R
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

链表的题目，这回不仅要找到倒数第 n 个结点，还要把之删掉，所以除了左右指针，我们再定义一个指针为 左指针的上一个结点，通过双指针法找到指针位置，如果此时 pre.next 还等于 head 的话，我们要删除 head 结点，所以要先让 head = l.next 再删去，其他情况直接删即可。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode l = head;
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode r = head;
        for (int i = 0; i < n && r != null; i++) {
            r = r.next;
        }
        while (r != null) {
            r = r.next;
            l = l.next;
            pre = pre.next;
        }
        if (pre.next == head) {
            head = l.next;
            pre.next = l.next;
        } else {
            pre.next = l.next;
        }
        return head;

    }
}

上述代码需要判断是否删除的是 head 的情况，但下面的代码，就不需要，思路：
使用 pre 作为 哨兵结点，就是头结点的前一个节点，然后，令 left 的起始位置等于这里，这样在双指针走完，left 会在 删除节点的前一个位置，最后删除，直接返回 pre.next 即可。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode l = pre;
        ListNode r = head;
        for (int i = 0; i < n && r != null; i++) {
            r = r.next;
        }
        while (r != null) {
            r = r.next;
            l = l.next;
        }
        l.next = l.next.next;
        return pre.next;

    }
}