1、Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

codes below

class MinStack {
private int size = 0;
private Node head = null;
class Node {
    int val;
    // every node contains min value at the moment it was pushed
    int min;
    Node next;
    Node(int v, int m) {val = v; min = m;}
}

public void push(int x) {
    int curMin = getMin();
    int newMin = x < curMin ? x : curMin;

    Node n = new Node(x, newMin);
    n.next = head;

    head = n;
    size++;
}

public void pop() {
    if (size <= 0)
        return;

    head = head.next;
    size--;
}

public int top() {
    if (size <= 0)
        return Integer.MAX_VALUE;

    return head.val;
}

public int getMin() {
    if (size <= 0)
        return Integer.MAX_VALUE;

    return head.min;
}}

这个使用ListNode的方法我还是没见过的。果然脑洞大开啊！