藍橋杯刷題JAVA（9）

黨課三日小鴿一手，今日繼續~其實該準備CSP了的說。。

1.最小棧

class MinStack {
    int val;
    private LinkedList<MinStack> stackList = new LinkedList<MinStack>();
	private LinkedList<Integer> minList = new LinkedList<Integer>();
	private int flag = 0;
	
	public MinStack() {
        this.val = Integer.MIN_VALUE;
    }
    
    public void push(int val) {
    	MinStack tempMinStack = new MinStack();
    	tempMinStack.val = val;
    	stackList.add(tempMinStack);
        if(minList.size() == 0)
            minList.add(val);
        else
    	    minList.add(Math.min(val, minList.getLast()));
	}
    
    public void pop() {
    	stackList.removeLast();
    	minList.removeLast();
    }
    
    public int top() {
    	return stackList.getLast().val;
    }
    
    public int getMin() {
    	return minList.getLast();
    }
}

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

經驗：

通過連結清單的方式來儲存棧裡的所有元素，本質上就是用棧實作的最小棧，極度浪費空間時間。。比較好的方法是在類中定義一個内部類的連結清單來實作。

2.相交連結清單

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) {
            return NULL;
        }
        ListNode *you = headA, *she = headB;
        while (you != she) { // 若是有緣，你們早晚會相遇
            you = you ? you->next : headB; // 當你走到終點時，開始走她走過的路
            she = she ? she->next : headA; // 當她走到終點時，開始走你走過的路
        }
        // 如果你們喜歡彼此，請攜手一起走完剩下的旅程（将下面這個 while 塊取消注釋）。
        // 一路上，時而你踩着她的影子，時而她踩着你的影子。漸漸地，你變成了她，她也變
        // 成了你。
        /* while (she) {
            you = she->next;
            she = you->next;
        } */
        return you;
    }
};
           

經驗：

此題解法巧妙，還能賦予愛情意義，目前最佳題沒有之一