剑指offer15——链表中倒数第K个结点

思路：

1. 使用堆栈，全部push进去pop出第k个结点
2. 两个指针，第一个先走k步，再第二指针开始走，k走到底的时候，第二个指针指向倒数第k+1个，这里有可能有歧义，（链表的最后是null，还是最后一个不为null的结点。）会影响代码的逻辑。

static int getKNum(ListNode root, int k) throws Exception {
    if (root == null) {
        throw new Exception("root is null");
    }
    Stack<ListNode> stack = new Stack<>();
    ListNode temp = root;
    while (temp.next != null) {
        stack.push(temp);
    }
    ListNode num = null;
    while (k!=0) {
        if (stack.isEmpty()) {
            throw new Exception("don't have k num");
        }
        num = stack.pop();
        k--;
    }
    if (num == null) {
        throw new Exception("don't have k num");
    }
    return num.value;
}

static int getKNum1(ListNode root, int k) throws Exception {
    if (root == null || k == 0) {
        throw new Exception("root is null or k = 0");
    }
    int k1 = k;
    ListNode firstIndex = root;
    ListNode afterIndex = root;
    while (k1 > 1 && firstIndex.next != null) {
        firstIndex = firstIndex.next;
        k1--;
    }
    if (k1 > 1) {
        throw new Exception("don't have k num");
    }
    while (firstIndex.next != null) {
        firstIndex = firstIndex.next;
        afterIndex = afterIndex.next;
    }
    return afterIndex.value;
}