19. Remove Nth Node From End of List

问题

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

思路

这是链表中非常常见的问题，众所周知，链表慢就慢在遍历查找，而对于单链表来说，每次必须从头开始搜索，这样使得链表在处理“倒数”这个概念的时候，特别无力。常规的做法必须要2遍遍历：1遍计算链表长度len，1遍搜索倒数的元素len-n。(当然，你可以通过加入链表长度变量或者使用双向链表解决这个问题。)

但是题目要求是一遍完成，有没有一遍的思路呢？其实是有的，那就是双指针或递归。

思路一 ——双指针

这里有个常用的做法去解决“倒数问题”：双指针。

双指针常用做法是：

• 一个指针用来作为参考，控制长度（作为循环停止条件）
• 一个指针延迟启动用来跑“倒数”。

第一个指针先运行n个数，然后打开第二个指针，这样，当第一个指针跑完时，第二个指针刚好跑过Len-N数，这样就找到了倒数第n个数。

注意：由于删除操作比较特殊，必须找到前一个节点才能删除下个节点，所以一般删除操作我们会构造一个虚拟节点作为开头，以防开头节点被删除。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(-1);  //防止头被删除
        newhead.next = head;
        ListNode point1 = newhead;
        ListNode point2 = newhead;
        for(;point1 != null;point1 = point1.next,n--)  //point1 控制长度
        {
            if(n < 0)
                point2 = point2.next;   //point2延迟启动
        } 
        point2.next = point2.next.next;
        return newhead.next;
    }
}

思路二 —— 递归

除了用双指针外，还可以考虑用递归，凡是这种涉及单链表插入删除操作的时候，都可以考虑用递归，因为插入和删除都需要涉及它的父亲操作。我们考虑最后一个元素是第一层，然后逐级返回，当返回到第N+1层（也就是父亲节点所在层数）就开始删除操作。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(-1);
        newhead.next = head;
        remove(newhead,n); 
        return newhead.next;
    }
    private int remove(ListNode node, int n) {
        if(node.next == null) return 1;
        int level = remove(node.next,n)+1; //层数+1
        if(level == n+1)    //找到了父亲
            node.next = node.next.next;
        return level;   
    }
}