#leetcode19.删除链表中倒数第k个节点/输出链表中倒数第k个节点

 这里是删除链表的倒数第k个节点，类似的问题是剑指offer上的返回链表的倒数第k个节点，其实是一类问题，不过返回链表的倒数第k个节点要稍微简单点，只要能找到就ok，而删除的话要把倒数第n-1和倒数第n-3节点给连接起来，稍微麻烦点，先来看返回倒数第k个节点的做法：

1、双节点法：

 public ListNode FindKthToTail(ListNode head,int k){

        if(head == null || k == 0)
            return null;
        ListNode fast = head;
        while(k-- >0) {
            if (fast == null)
                return null;
            fast = fast.next;
        }

        ListNode slow = head;

        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

因为本人有点菜，所以写这段代码的时候碰到了先写fast = fast.next;后判断还是先判断后写fast = fast.next的问题，考虑了一下将过程手画了一下，如果后判断fast == null的话，当k=0的时候，

会因为满足fast==null 而直接return null了，如果是先判断，它会自然的走下一次循环，而下一次循环因为k不再大于0导致退出循环，因此会得到正确的结果。

再看一下递归的写法：

private int count = 0;
    private ListNode pHead = null;

    public ListNode FindKthToTail(ListNode head,int k){

        if (head == null || k==0)
            return null;

        recListNode(head,k);
        return pHead;
    }

    private void recListNode(ListNode head, int k) {
        if (head == null)
            return;
        recListNode(head.next,k);
        count++;
        if(count == k) {
            pHead = head;
        }
    }

这是递归的写法，思路也比较简单，就是用一个全局变量来存储倒数节点的位序，另一个ListNode全局引用，当计数个数达到了想要的倒数个数的时候，就可以将当前的head赋值给引用变量，主函数里面返回就可以了～

如果变一下，要求删除倒数第k个节点的话，应该怎么做呢？

看下代码：

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while(n-- >0) {
            fast = fast.next;
        }
        if( fast ==null) {
            return head.next;
        }

        ListNode slow = head;
        while(fast.next!= null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;

        return head;
    }

这里使用的是双节点的方法，我考虑了一下，用递归不太好实现，因为需要返回删除后的链表的首节点，需要先知道链表的长度，然后用count进行计数？ 同时递归函数里面的参数是局部变量，对齐进行修改之后，原函数的链表的首节点的后续节点其实并没有发生变化，所以用双节点的方法来实现相对更优雅一些！