150. Evaluate Reverse Polish Notation Leetcode Java

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

A stack is used in my solution to realize the calculating of the reverse polish notation. Here we suppose the input are all good. 

Each time when we encounter a operators we pop out two integers from the stack to form the expression and calculate the current result and push it back to the stack.

 public ListNode sortList(ListNode head) {  
     return mergeSort(head);  
   }  
   public ListNode mergeSort(ListNode head){  
     if(head==null || head.next==null) return head;  
     ListNode runner=head.next;  
     ListNode walker=head;  
     while(runner!=null && runner.next!=null){  
       walker=walker.next;  
       runner=runner.next.next;  
     }  
     ListNode head2=walker.next;  
     walker.next=null;  
     return MergeTwo(mergeSort(head),mergeSort(head2));  
   }  
   public ListNode MergeTwo(ListNode l1,ListNode l2){  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=l1;  
     ListNode pre=preDummy;  
     while(pre.next!=null && l2!=null){  
       if(pre.next.val>l2.val){  
         ListNode temp=l2.next;  
         l2.next=pre.next;  
         pre.next=l2;  
         l2=temp;  
       }  
       pre=pre.next;  
     }  
     if(pre.next==null) pre.next=l2;  
     return preDummy.next;  
   }