剑指 - 链表中倒数第k个结点

题目

输入一个链表，输出该链表中倒数第k个结点。

思路

两种方案，不过空间复杂度都为 O(n)，可以考虑一种计数后再次遍历，空间复杂度 O(1)，但写起来比较麻烦，这里就记录比较容易实现和理解的两种方案了

public class LinkListKthNode {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        return sol2(head, k);
    }

    //第一种方案 ： 栈
    private ListNode sol1(ListNode head, int k) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        if (stack.size() < k) {
            return null;
        }
        while (k > 1) {
            stack.pop();
            k--;
        }
        return stack.pop();
    }

    //第二种方案： 存下读取
    private ListNode sol2(ListNode head, int k) {
        ListNode p = head;
        ArrayList<ListNode> list = new ArrayList<>();
        while (p != null) {
            list.add(p);
            p = p.next;
        }
        if (list.size() < k) {
            return null;
        }
        return list.get(list.size() - k);
    }
}

总结

基础题，不用额外空间的写起来比较臃肿