【剑指Offer 15】链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，本题从1 开始计数，即链表的尾结点是倒数第1 个结点．例如一个链表有6 个结点，从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点。

代码如下：

package demo;

public class Test14 {
    public static class ListNode {
        int value;
        ListNode next;
    }

    public static ListNode findKthToTail(ListNode head, int k) {
        // 链表不能为null，k必须大于0
        if(head == null || k < 1) {
            return null;
        }
        ListNode behindPointer = head;
        ListNode aheadPointer = head;
        for(int i = 0; i < k-1; i++) {
            if(aheadPointer.next != null) {
                aheadPointer = aheadPointer.next;
            } else {
                return null;
            }
        }
    
        while(aheadPointer.next != null) {
            aheadPointer = aheadPointer.next;
            behindPointer = behindPointer.next;
        }
    
        return behindPointer;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.value = 1;
        head.next = new ListNode();
        head.next.value = 2;
        head.next.next = new ListNode();
        head.next.next.value = 3;
        head.next.next.next = new ListNode();
        head.next.next.next.value = 4;
        head.next.next.next.next = new ListNode();
        head.next.next.next.next.value = 5;
        head.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.value = 6;
    
        System.out.println("尾结点：");
        System.out.println(findKthToTail(head, 1).value);
        System.out.println("头结点：");
        System.out.println(findKthToTail(head, 6).value);
        System.out.println("第3个结点：");
        System.out.println(findKthToTail(head, 3).value);
        System.out.println("头结点为null：");
        System.out.println(findKthToTail(null, 1));
        System.out.println("链表结点个数小于k：");
        System.out.println(findKthToTail(head, 10));
        System.out.println("k为0：");
        System.out.println(findKthToTail(head, 0));
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46669025