Day 74, ##, Sort List, Evaluate Reverse Polish Notation

Sort List
Sort a linked list in O(n log n) time using constant space complexity.
-----------------------------------------------------------------
Solution #1, recursive merge sort
wiki page has iterative buttom-up method
http://en.wikipedia.org/wiki/Merge_sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge (ListNode *&left, ListNode *&right) {
        ListNode* dummy = new ListNode(INT_MIN); // dummy
        ListNode* itr = dummy;
        while (left != NULL && right != NULL) {
            if (left->val <= right->val) {
                itr->next = left;
                itr = left;
                left = left->next;
            }else {
                itr->next = right;
                itr = right;
                right = right->next;
            }
        }
        if (right == NULL) itr->next = left;
        if (left == NULL) itr->next = right;
        return dummy->next;
    }

    ListNode *sortList(ListNode *head) {
        // divide
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode *slow = head, *fast = head->next;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                fast = fast->next;
                slow = slow->next;
            }
        }
        ListNode *second = slow->next;
        slow->next = NULL;
        
        head = sortList(head);
        second = sortList(second);
        
        // merge
        return merge(head,second);
    }
};

Update Jan-5-2015
dummy should be deleted in merge

Evaluate Reverse Polish Notation
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

----------------------------------------------------
post order, using stack
注意从stack出来时的顺序，RPN是最先进stack的在前面。

class Solution {
public:
    int arith (int op1, int op2, string opt) {
        if (opt == "+") {
            return op1 + op2;
        }else if (opt == "-") {
            return op1 - op2;
        }else if (opt == "*") {
            return op1 * op2;
        }else if (opt == "/") {
            return op1 / op2;
        }
    }

    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        int num = 0;
        for (int i = 0; i < tokens.size(); i++) {
            if (isdigit(tokens[i][0]) || (tokens[i].length() > 1 && isdigit(tokens[i][1]))) {
                num = atoi(tokens[i].c_str());
            }else {
                int operand1 = s.top();
                s.pop();
                int operand2 = s.top();
                s.pop();
                num = arith(operand2,operand1,tokens[i]);
            }
            s.push(num);
        }
        return num;
    }
};