力扣刷题之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

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

思路是这样的：

        设置一个结点指向头结点，这个结点成为哨兵，哨兵的作用是在处理边界问题的时候会变的很方便，就像遇到了一个空链表，如果我们在不知情的情况下访问了头结点的next结点，可能会产生空指针异常。所以设置了哨兵的话就能保证怎么着都有一个结点能访问。还有一个就是能让我们清晰的知道这个链表的头/尾在哪。

        接下来要做的事情就很简单了，设置两个新的结点指向哨兵结点，定为结点1和2。让结点1先移动n+1位，这个n就是方法中传入的倒数第n位。然后两个指针再同时向前移动，直到结点1到达链表末尾。这个时候结点2所指向的结点的下一个结点，就是我们要删除的结点。把当前指向换成下一个的下一个，也就是结点2.next.next。这样就删除完成了，最后直接返回哨兵结点指向的下一个结点即可。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fitst = new ListNode(0);
        fitst.next = head;
        
        ListNode node1 = fitst;
        ListNode node2 = fitst;
        
        for (int i = 1; i <= n + 1; i++) {
            node1 = node1.next;
        }
        
        while (node1 != null) {
            node1 = node1.next;
            node2 = node2.next;
        }
        
        node2.next = node2.next.next;
        return fitst.next;
    }
}

这样也能用一遍扫描实现了（吧，懂得麻烦看一下，应该是一遍扫描就行了） 

（算法大佬英雄哪里出来曾曰：过——啦）

解决。