Q：链表的倒数第K个元素

问题：如何得到链表中的倒数第k个元素?

??一种简单的思路是遍历链表一遍，并统计出链表中节点的数目，然后计算出倒数第k个元素到链表头节点的元素的距离，然后得到对应的结果。但是，我们能否有一种更加简便的方式来得到倒数的第k个元素的结果呢？答案肯定有啦，不然我也不会总结成博文了.....哈哈哈哈~

??具体的解题步骤如下：

1. 初始化两个指针a和b，其均指向链表头节点。
2. b指针先走k-1步
3. a指针和b指针均同时走一步
4. 重复步骤3，直到b指针走到链表末尾节点，此时，a指针所指向的链表节点，即为其对应的链表中的倒数第k个元素

具体代码实现如下：

/**
 * @author 学徒
 *用于获取链表中的倒数第k个元素的节点值
 */
public class ReverseKth {
    /**
     * 链表元素的节点
     * @param  值类型
     */
    static class Node{
        //节点值
        T value;
        //节点的下一个节点的指针
        Node next;
        public Node(T value){
            this(value,null);
        }
        public Node(T value,Node next){
            this.next=next;
            this.value=value;
        }
    }

    public Node getKth(Node head,int k){
        Node a=head,b=head;
        for(int i=0;i a=new Node("A");
        Node b=new Node("B");
        Node c=new Node("C");
        Node d=new Node("D");
        Node e=new Node("E");
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=e;
        ReverseKth list=new ReverseKth();
        Node result=list.getKth(a,2);
        System.out.println(result.value);
    }

}

回到目录|·(工)·）