输出单向链表中倒数第K个节点，比如我们现在有int类型的1,2,3,4,5,6,7,8组成的一个单向链表，求倒数第三个元素。如图所示：

    我们正常的思路就是从后往前推倒数第K个元素，这里有这样几个问题。首先是单向链表的限制，链表节点只有next指针指向下一个元素，所以我们只能从前往后推；其次我们需要知道最后一个元素后才能从后往前倒推，这里就只能通过next指针由前往后遍历，这是第一次循环，然后从后往前推又要开始遍历，这是第二次循环；另外如果从后往前推这也是个问题；或者说第一次循环时知道了单项链表长度，然后通过倒数第K个，我们能推导出是正数第几个，这样再从前往后循环一次就能获取这个节点，但是这样还是循环了两次。

    这里我们只介绍目前了解到的最优的解决方案，其他方法就不一一介绍了。

    我们通过两个指针和一次循环就能得到想要的节点，步骤如下：

1. 最后一个节点与倒数第K个节点之间的距离为K-1。指定两个指针P1和pP2，P1从头结点开始先移动K-1步，停下来。
2. P1停下来后，P2指向第一个节点，注意此时P1与P2之间的距离正好是最后一个节点和倒数第K个节点间的距离。
3. P1和P2同时向后移动，当P1移动到最后一个节点的位置时停下来，此时P2的位置就正好是倒数第K个元素的位置了，那么P2处的节点就是我们想要的倒数第K个节点。

    我们可以按上图中的链表来试算下。有 1,2,3,4,5,6,7,8这样顺序的一个单项链表，求倒数第3个节点。倒数第三个节点与最后一个节点的距离是3-1=2。先定义P1指针，从头节点移动2步，到达节点3的位置停下来，这时定义P2节点指向头节点，也就是节点1，然后P1和P2节点同时向后移动，当P1节点移动到最后一个节点8时，此时P1移动到了节点6处，而节点6就是倒数第3个节点，ok，节点6就是我们要的节点。

    代码实现：

public class SingleLinkedNode {    //节点上存储的数据    private Object data;    //该节点的下一个节点    private SingleLinkedNode next;    public SingleLinkedNode(Object data){        this.data = data;    }       ......}

public static SingleLinkedNode getReverseKPathNode(SingleLinkedNode head , int  k){        //定义两个指针P1和P2，这里直接用节点表示        SingleLinkedNode P1 = head;        SingleLinkedNode P2 = head;        //P1移动到K-1位置停下来        for(int i=1;i<=k-1;i++){            P1=P1.getNext();        }        //P1和P2同时向后移动，直到P1节点移动到最后一个节点        while(P1.getNext()!=null){            P1 = P1.getNext();            P2 = P2.getNext();        }        //此时P2节点就是倒数第K个节点        return P2;}

    测试：

public static void main(String[] args){        SingleLinkedNode node1 = new SingleLinkedNode(1);        SingleLinkedNode node2 = new SingleLinkedNode(2);        SingleLinkedNode node3 = new SingleLinkedNode(3);        SingleLinkedNode node4 = new SingleLinkedNode(4);        SingleLinkedNode node5 = new SingleLinkedNode(5);        SingleLinkedNode node6 = new SingleLinkedNode(6);        SingleLinkedNode node7 = new SingleLinkedNode(7);        SingleLinkedNode node8 = new SingleLinkedNode(8);        node1.setNext(node2);        node2.setNext(node3);        node3.setNext(node4);        node4.setNext(node5);        node5.setNext(node6);        node6.setNext(node7);        node7.setNext(node8);        System.out.println(getReverseKPathNode(node1,3).getData());}

    执行结果为：6,。正确