###### tags: `Leetcode` `不懂`
# 0019. 删除链表的倒数第N个节点（递归不懂）
Link: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
## 注意
我在92里说```在链表的反转中加入虚拟头节点是一般常用的做法```，现在我发现涉及链表的增删改操作的，加入虚拟头节点都会方便很多。查还不清楚。

## 思路

## Keypoints
## Code in C++

## Code in Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(-1, head);
        ListNode front = head;
        for (int i = 0; i < n; i++) {
            front = front.next;
        }
        ListNode rear = dummyHead;
        while (front != null){
            front = front.next;
            rear = rear.next;
        }
        rear.next = rear.next.next;
        return dummyHead.next;
    }
}

## 思路1
### 一次遍历
暴力解法就是先遍历一遍得到链表的长度，第二次遍历找到倒数第 $N$ 个节点然后删除。

显然这不够厉害，厉害的做法就是

* 先让一个节点```front```走到第 $N+1$ 个节点那里（有可能得到```front = null```，不过没有影响）
* 然后在让一个节点```rear```从虚拟头节点开始和```front```一起走，当```front```走到```null```的时候，```rear```正好走到了倒数第 $N$ 个节点的前一个节点。
* ```rear.next = rear.next.next```即可。

可以看出第二步想让```rear```走到了倒数第 $N$ 个节点的前一个节点，那么如果倒数第 $N$ 个节点恰好是头节点呢，没有关系，我们还有虚拟头节点在头节点前边。

所以虚拟头节点在链表里很有用！

## 思路2
### 递归
递归的操作有点秀
可惜看不懂

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        return removeNode(head,n) == n ? head.next : head;
    }
    public int removeNode(ListNode node,int n) {
        if(node.next == null)  return 1;
        int m = removeNode(node.next, n);
        if(m == n)
            if(m == 1) node.next = null;
            else node.next = node.next.next;
        return m + 1;
    }
}

class Solution {
    int cur = 0;
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        if (head == null) return null;
        head.next = removeNthFromEnd1(head.next, n);
        cur++;
        if (n == cur) return head.next;
        return head;
    }
}