链表中倒数第K个节点

题目：

​ 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从 1 开始，即链表的尾结点是倒数第 1 个节点。例如，一个链表有6个节点，从头结点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第三个节点是值为 4 的节点。链表定义如下：

public class ListNode {
    public int value;
    public ListNode next;
}

分析：

​ 最常见的方法是先把整个链表遍历一遍，获取到链表的节点总数 n。然后在遍历第二次，获取第 n-k+1 个节点即可。这种方法要把链表遍历两次，虽然可以解决问题，但却不是最好的方案。

优化方案：

​ 定义两个指针 firts 和 second，first 从头开始遍历，移动 k-1 位后，second 开始移动。当 first 移动到链表的尾端时，second 刚好位于第 k 个节点上。代码实现如下：

public class GetLastNumNode {

    public static ListNode getNode(ListNode pHead, int k) {
		// 链表为空或者k=0，直接返回null
        if (null == pHead || k == 0) {
            return null;
        }

        ListNode firstNode = pHead;
        ListNode secondNode = pHead;

        int count = 0;
        while (firstNode.next != null) {
            // 当第一个节点移动到 k-1 位时，第二个节点开始移动
            if (count >= k - 1) {
                secondNode = secondNode.next;
            }

            firstNode = firstNode.next;
            count++;
        }
		// 如果k大于链表节点总数，count无法大于等于k-1，输入参数有误，返回null
        if (secondNode == pHead) {
            return null;
        }

        return secondNode;
    }
}