面试题22：链表的倒数第k个节点

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

思路：采用双指针找到倒数第k个节点。设立两个指针，第一个指针先走k-1步，第二个指针此时开始和第一个指针一起出发，保证两个指针的索引之和为k+1。

代码如下：

public class FindKthFromLinkList {
    public class ListNode{
        int val;
        ListNode next = null;

        ListNode(int val){
            this.val = val;
        }
    }

    public ListNode FindKthToTail(ListNode head,int k) {
         if (head == null || k==0){
             return null;
         }
         int length = 1;
         ListNode p = head;
         while (p.next != null){
             length++;
             p = p.next;
         }
         if (k>length){
             return null;
         }
         ListNode node = head;
         for (int i=1;i<length-k+1;i++){
             node = node.next;
         }
         return node;
    }
    public ListNode FindKthToTail1(ListNode head,int k) {
        if (head == null || k==0){
            return null;
        }
        ListNode node = head;
        ListNode listNode = head;

        for (int i=0;i<k-1;i++){
            if (node.next == null){
                return null;
            }
            node = node.next;
        }
        ////从k开始，同时进行，保证和为k+1
        while (node.next != null){
            node = node.next;
            listNode = listNode.next;
        }

        return listNode;
    }
}

启发：
如果在链表中寻找节点类似的题目可以考虑用多指针的形式，一般是其中一个指针先走几步，然后同时走，或者其中一快一慢两个指针的形式解决问题
例如找链表的中间节点，可以设置快慢指针，2倍的关系，当快指针到达最后一个节点时，即慢指针到达了中间节点。