蓝桥杯刷题JAVA（9）

党课三日小鸽一手，今日继续~其实该准备CSP了的说。。

1.最小栈

class MinStack {
    int val;
    private LinkedList stackList = new LinkedList();
	private LinkedList minList = new LinkedList();
	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;
    }
};

经验： 此题解法巧妙，还能赋予爱情意义，目前最佳题没有之一