LCOF22

[underwindfall]

• https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

• 思路

  • 双指针
  • stack
  • recursive

• [x] 刷15mins

• [x] 刷5mins

/**
     * 顺序查找
     * 先走k步，慢指针然后再走
     * time O(n)
     * space O(1)
     */
    class DoubleIndex {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode former = head, latter = head;
            for (int i = 0; i < k; i++)
                former = former.next;
            while (former != null) {
                former = former.next;
                latter = latter.next;
            }
            return latter;
        }
    }

    // time O(n)
    // space O(1)
    class Recursive {
        public ListNode getKthFromEnd(ListNode head, int k) {
            return dfs(head, k).getKey();
        }

        Pair<ListNode, Integer> dfs(ListNode head, int k) {
            if (head.next == null) {
                return new Pair<>(head, 1);
            }
            Pair<ListNode, Integer> next = dfs(head.next, k);
            if (next.getValue() == k) {
                return next;
            }
            return new Pair<>(head, next.getValue() + 1);
        }

        class Pair<ListNode, Integer> {
            ListNode key;
            Integer value;

            Pair(ListNode key, Integer value) {
                this.key = key;
                this.value = value;
            }

            ListNode getKey() {
                return key;
            }

            Integer getValue() {
                return value;
            }
        }
    }

    // time O(n)
    // space O(n)
    class StackSolution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            Stack<ListNode> stack = new Stack<>();
            ListNode tmp = head;
            while (tmp != null) {
                stack.push(tmp);
                tmp = tmp.next;
            }
            while (!stack.isEmpty() && k > 1) {
                stack.pop();
                k--;
            }
            return stack.peek();
        }
    }