T19删除链表的倒数第N个节点——Java实现

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

• 常规方法…
• 先计算，是正数第size-n个
• 设置一个变量，标记节点走一步就+1，直到定位到目标节点为止

• 使用快慢双指针firstNode以及lastNode

• 开始时，firstNode指针指向head，而lastNode指针需要先指向一个哑节点，定位到目标节点的前驱节点，便于删除节点

• 哑节点：ListNode dummyNode = new ListNode(0,head)；这样哑节点的下一个节点就是头节点了

public ListNode removeNthFromEnd(ListNode head, int n) {
        //使用快慢指针
        //设first指针先走n步，当它刚走n步的时候，last指针就开始跟着first指针一起走

        ListNode firstNode = head;
        ListNode dummyNode = new ListNode(0,head);
    	ListNode lastNode = dummyNode;
        int count = 0;
    //这里会有点绕，关于什么时候lastNode开始移动，官方解答在一个循环里让firstNode先走，很容易懂
        while(firstNode.next != null){
            firstNode = firstNode.next;
            count++;
            if(count>=n){
                lastNode = lastNode.next;
            }
        }
    //我这里还考虑了是否删除的是原头节点，与官方解答比起来，就很多余
    //没有考虑到dummyNode节点的下一个节点就是新的头节点
        if (lastNode.next == head){
            return head.next;
        }

        lastNode.next = lastNode.next.next;
        return head;
    }

 public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
     //直接返回哑节点的下一个节点了，不管删除的是不是原先的头节点
        ListNode ans = dummy.next;
        return ans;
    }

• 如果删除的是头节点怎么办，使用双指针的时候我要怎么定位它，以及怎么删除它，没有想到可以设置一个哑节点
• 使用while循环让firstNode先走，在判断lastNode什么时候走的时候脑袋有点混乱