【剑指Offer1】包含min函数的栈、从尾到头打印链表

最开始图省事，搞了一个list，在min函数被调用时将栈内现有数据全部排序后返回最小值

由于性能太差，考虑一个新的思路

设计思路：
由两个栈组成，A栈作为元素栈，B栈作为最小元素栈
push元素进栈时，和B栈栈顶元素比较，如果更小或相等则压入，否则不处理
pop元素出栈时，和B栈栈顶元素比较，如果相等则B栈也弹出元素
min方法直接返回B栈栈顶元素即可

--解答错误
在执行push时，如果相等元素再次压入，需要在B栈也做压入处理，防止A栈有多个最小元素，弹出一个后B栈为空，导致结果出错

class MinStack {

    Stack a = null;
    Stack b = null;

    /** initialize your data structure here. */
    public MinStack() {
        a = new Stack<>();
        b = new Stack<>();        
    }
    
    public void push(int x) {
        a.push(x);
        if (b.isEmpty() || b.peek() >= x) {
            b.push(x);
        }
    }
    
    public void pop() {
        if (!b.isEmpty() && b.peek().equals(a.pop())) {
            b.pop();
        }
    }
    
    public int top() {
        return a.peek();
    }
    
    public int min() {
        if (b.isEmpty()) {
            return a.peek();
        } else {
            return b.peek();
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

下一题因为太简单也放在这里

逆向打印输入的数组，简单的递归，跳出条件是链表下一节点为空

注意处理一下空数组输入导致的空指针问题即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        List list = new ArrayList<>();
        reverse(head, list);  
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public void reverse(ListNode head, List list) {
        if (head.next != null) {
            reverse(head.next, list);
        }
        list.add(head.val);
    }
}