【每天一题】获取单向链表的倒数第K个元素

思路：无论如何，如果不借助于辅助数据结构，那么链表的某些元素肯定需要被遍历两遍。

在使用辅助的数据结构的情况下，可以采用如下方案：

遍历的同时将每个节点的地址和序号记录在一个足够大的数组中，等到遍历完成时就可以从数组中找到倒数第K个元素。这肯定不是出题人的本意。

 

在对链表遍历两遍的情况下，可以有两种方案：

1、用两个指针，一个指针先走K步，然后第二个指针再从头开始，这样当地一个指针走到尾节点时，第二个指针的位置就是所需要的节点位置。

2、先遍历一遍链表得到链表的长度N，然后再从头遍历，直到第N-K个节点。

 

两种方法无优劣之分，但是前者显然更有“创意”，下面就方案1给出代码：

 

package get.lastk.element; 

public class Node 
{ 
    private int data; 
    private Node next; 

    private static int i = 0; 

    public Node(int data) 
    { 
        this.data = data; 
        System.out.println("The " + i++ + "th Node is " + data + "."); 
    } 


    public Node getNext() 
    { 
        return next; 
    } 

    public void setNext(Node next) 
    { 
        this.next = next; 
    } 

    public int getData() 
    { 
        return data; 
    } 

    public void setData(int data) 
    { 
        this.data = data; 
    } 
}

package get.lastk.element; 

import java.util.Random; 

public class TestMain 
{ 

    public static void main(String[] args) 
    { 
        /* 
         * create a node list. 
         */ 
        final int bound = 2000; 
        Random random = new Random(System.currentTimeMillis()); 
        Node listRoot = new Node(random.nextInt(bound)); 
        Node next = new Node(random.nextInt(bound)); 
        listRoot.setNext(next); 
        Node lastNode = null; 
        for (int i = 0; i != 18; i++) 
        { 
            lastNode = next; 
            next = new Node(random.nextInt(2000)); 
            lastNode.setNext(next); 
        } 

        final int k = 50; 
        Node kthNode = getKthElementBackWords(listRoot, k); 
        if (kthNode != null) 
        { 
            System.out.println(kthNode.getData()); 
        } 
        else 
        { 
            System.out.println("The " + k + "th node is null."); 
        } 
    } 

    public static Node getKthElementBackWords(final Node root, int k) 
    { 
        if (root == null || k <= 0) 
        { 
            return null; 
        } 

        Node firstNode = root; 
        Node secondNode = root; 
        while (--k >= 0 && firstNode != null) 
        { 
            firstNode = firstNode.getNext(); 
        } 

        if (firstNode == null) 
        { 
            return null; 
        } 

        while (firstNode != null) 
        { 
            firstNode = firstNode.getNext(); 
            secondNode = secondNode.getNext(); 
        } 
        return secondNode; 
    } 
}