剑指offer系列之十三：链表中的倒数第k个节点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

举一个简单的例子，比如链表{1,2,3,4,5}，如果要返回倒数第二个节点，也就是k=2，就相当于正数第5-k+1=4个节点，所以我们可以采用两次循环：一次循环得到链表的结点个数；另一次循环则是从链表中找到第n-k+1个节点。虽然是两次循环，但时间复杂度是O(n)，需要注意的是，这里仍然需要对链表的边界条件进行判断。基于这种思路写出如下代码：

public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k <= 0) return null;
        int nodesNum = 1;
        ListNode node = head;
        while(node.next != null){
            nodesNum++;
            node = node.next;
        }
        int i = 1;
        node = head;
        while(k <= nodesNum && i != nodesNum - k + 1){
            i++;
            node = node.next;
        }
        if(k <= nodesNum)
            return node;
        return null;
    }

还有一种思路就是创建两个指针，一个指针先走k-1部，当第k部的时候，另一个指针从第一个节点开始走，这样，第一个指针到达最后一个指针的时候，第二个指针刚好到达倒数第k个节点的位置。实现代码如下（已被牛客AC）：

public ListNode FindKthToTail2(ListNode head,int k) {
        if(head == null || k <= 0) return null;
        ListNode pre = head;
        ListNode behind = null;
        for (int i = 0; i < k - 1; i++) {
            if(pre.next != null){
                pre = pre.next;
            }else {
                return null;
            }
        }

        behind = head;
        while(pre.next != null){
            pre = pre.next;
            behind = behind.next;
        }
        return behind;
    }