not correct~

MaxStack.java

class Solution {
  class ListNode {
    int val;
    ListNode oldNode = null; // point to old max node
    ListNode prev = null;
    ListNode next = null;
    ListNode(int _val) { val = _val; }
  }

  ListNode dummy = new ListNode(0);
  ListNode dummyTail = new ListNode(0);
  ListNode maxNode = new ListNode(Integer.MIN_VALUE);

  MaxStack() {
    dummy.next = dummyTail;
  }

  // helper
  private ListNode addFirst(int x, ListNode oldMax) {
    ListNode newNode = new ListNode(x);
    newNode.oldNode = oldMax;
    newNode.next = dummy.next;
    newNode.next.prev = newNode; // if no dummyTail, get NullPointerException
    newNode.prev = dummy;
    dummy.next = newNode;
    return newNode;
  }

  private ListNode removeFirst() {
    ListNode removed = dummy.next;
    dummy.next = removed.next;
    dummy.next.prev = dummy;
    removed.prev = removed.next = null;
    return removed;
  }

  public void push(int x) {
    if (x >= maxNode.val) {
      // push the old maxNode
      addFirst(maxNode.val, maxNode);
      maxNode = addFirst(x, null);
    } else {
      addFirst(x, null);
    }
  }

  public int pop() {
    ListNode x = removeFirst();
    if (x.val == maxNode.val) { // restore
      ListNode backupNode = removeFirst();
      maxNode = backupNode.oldNode;
      backupNode.oldNode = null;
    }
    return x.val;
  }

  public int top() {
    return dummy.next.val;
  }

  public int peekMax() {
    return maxNode.val;
  }

  public int popMax() {
    int max = maxNode.val;
    // prevNode -> maxNode -> backupNode -> nextNode
    // prevNode -> nextNode
    ListNode prevNode = maxNode.prev;
    ListNode backupNode = maxNode.next;
    ListNode nextNode = maxNode.next.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
    // clear & update maxNode
    backupNode.prev = backupNode.next = null;
    maxNode.prev = maxNode.next = null;
    maxNode = backupNode.oldNode;
    backupNode.oldNode = null;
    return max;
  }
}