19.删除单链表倒数第n个数

题目描述：

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

解答：

解答1:遍历两遍链表

首先是普通的解法。
删除节点怎么实现呢?假设链表按x->y->z排列,要删除第y个节点，就是x.next = x.next.next ,即要找到被删除节点的上一个节点。
那么如何找到被删除的节点y的上一个节点x呢？先通过一轮遍历，获得链表长度length，当前被删除节点的序号则是 length-n+1，前一个节点x的序号就是length-n 。在这里可以用一个指针指向头结点，从头节点一路next,一步一步最终指向x节点，从头节点head走到x要这一过程经过length-n-1步。
这样大致的思路就出来了，但是还要考虑到几个特殊情况，比如链表长度可能为1或者要删除的节点就是头结点，这样就不存在前一节点了。

//遍历两遍
        ListNode p=head;
        int count=0;
        while(p!=null){
            //先获得链表长度
            count++;
            p=p.next;
        }
        if (count<=1) {
            return null;
        }
        if (n>count) {
            return head;
        }
        if (n==count) {
            return head.next;
        }
        p=head;
        //被删除节点的序号是 length-n+1；所以一直遍历到要删除节点的前一个位置序号是length-n
        for(int i=0;i<count-n-1;i++){
            p=p.next;
        }
        p.next=p.next.next;
        return head;

解答2:遍历一遍

典型的利用双指针法解题。首先让指针fast指向头节点，然后让其向后移动n步，接着让指针slow指向头结点，并和fast一起向后移动。当fast的next指针为NULL时，slow即指向了要删除节点的前一个节点，接着让fast指向的next指针指向要删除节点的下一个节点即可。注意如果要删除的节点是首节点，那么first向后移动结束时会为NULL，这样加一个判断其是否为NULL的条件，若为NULL则返回头结点的next指针。

if (head==null) {
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        for (int i = 0; i < n; i++) {
            fast=fast.next;
        }
        if (fast==null) {
            head=head.next;
            return head;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return head;

时间更快：

ListNode out = new ListNode(0);
        out.next=head;
        ListNode pListNode = out.next, rs = out;
        int i = 0;
        while (pListNode != null) {
            pListNode = pListNode.next;
            i++;
            if (i > n) {
                rs = rs.next;
            } 
        }
        rs.next=rs.next.next;
        return out.next;