分析：為了得到倒數(shù)第k個(gè)結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步。
可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。
既然不能從尾結(jié)點(diǎn)開始遍歷這個(gè)鏈表，我們還是把思路回到頭結(jié)點(diǎn)上來。假設(shè)整個(gè)鏈表有n個(gè)結(jié)點(diǎn)，那么倒數(shù)第k個(gè)結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第n-k-1個(gè)結(jié)點(diǎn)（從0開始計(jì)數(shù)）。
如果我們能夠得到鏈表中結(jié)點(diǎn)的個(gè)數(shù)n，那我們只要從頭結(jié)點(diǎn)開始往后走n-k-1步就可以了。
如何得到結(jié)點(diǎn)數(shù)n？這個(gè)不難，只需要從頭開始遍歷鏈表，每經(jīng)過一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。
這種思路的時(shí)間復(fù)雜度是O(n)，但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點(diǎn)個(gè)數(shù)n，第二次得到從頭結(jié)點(diǎn)開始的第n--k-1個(gè)結(jié)點(diǎn)即倒數(shù)第k個(gè)結(jié)點(diǎn)。如 果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。
但如果輸入的鏈表的結(jié)點(diǎn)個(gè)數(shù)很多，有可能不能一次性把整個(gè)鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個(gè)結(jié) 點(diǎn)需要兩次從硬盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時(shí)間的操作。
我們能不能把鏈表遍歷的次數(shù)減少到1？如果可以，將能有效地提高代碼執(zhí)行的時(shí)間效率。如果我們在遍歷時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個(gè)指針保持不動；在第k-1步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷。
由于兩個(gè)指針的距離保持在k-1，當(dāng)?shù)谝粋€(gè)（走在前面的）指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針（走在后面的）指針正好是倒數(shù)第k個(gè)結(jié)點(diǎn)。
這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個(gè)結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。因此這一方法的時(shí)間效率前面的方法要高。

定義結(jié)點(diǎn)：

/**
 * 節(jié)點(diǎn)
 */
public class Node {
    //數(shù)據(jù)域
    int data;
    //指針域
    Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;

    }

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

    public int getData() {
        return data;
    }

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

}

Java代碼實(shí)現(xiàn)：

 public static Node findKNode(Node head, int k) {
        if (head == null || k < 1) {
            return null;
        }
        Node firstNode = head;
        Node secondNode = head;
        for (int i = 0; i < k - 1; i++) {
            if (firstNode.next != null) {
                firstNode = firstNode.next;
            } else {
                return null;
            }
        }
        while (firstNode.next != null) {
            firstNode = firstNode.next;
            secondNode = secondNode.next;
        }
        return secondNode;
    }

測試代碼：

public class FindKNode {
    public static void main(String args[]) {
        //頭節(jié)點(diǎn)
        Node head = null;
        //當(dāng)前節(jié)點(diǎn)
        Node curNode = null;
        for (int i = 0; i < 10; i++) {
            if (i != 0) {
                Node node = new Node(i + 1);
                curNode.setNext(node);
                curNode = node;
            } else {
                head = new Node(i);
                curNode = new Node(i + 1);
                head.setNext(curNode);
            }

        }
        Node kNode = findKNode(head,5);
        System.out.println("倒數(shù)第K個(gè)節(jié)點(diǎn)是："+kNode.getData());
    }
  
}