445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/
Solution 1. Read the value to 2 vectors.
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> v1, v2;
        ListNode* ln, * res = nullptr;
        ln = l1;
        while(ln) {
            v1.push_back(ln->val);
            ln = ln->next;
        }
        ln = l2;
        while(ln) {
            v2.push_back(ln->val);
            ln = ln->next;
        }
        int NI = v1.size(), NJ = v2.size(), c = 0;
        for(int i=NI-1, j=NJ-1; i>=0||j>=0|| c; i--, j--, c/=10) {
            if(i>=0) c+=v1[i];
            if(j>=0) c+=v2[j];
            ln = new ListNode(c%10);
            ln->next = res;
            res = ln;
        }
        return res;
    }
Or use a stack:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1;
        stack<int> s2;
        ListNode* l = l1, * res=nullptr;
        while(l){
            s1.push(l->val);
            l = l->next;
        }
        l = l2;
        while(l) {
            s2.push(l->val);
            l = l->next;
        }
        l = nullptr;
        int c = 0;
        while(!s1.empty() || !s2.empty() || c) {
            if(!s1.empty()) {
                c += s1.top();
                s1.pop();
            }
            if(!s2.empty()) {
                c += s2.top();
                s2.pop();
            }
            l = new ListNode(c%10);
            l->next = res;
            res = l;
            c /= 10;
        }
        return res;
    }

503. Next Greater Element II

https://leetcode.com/problems/next-greater-element-ii/description/
    vector<int> nextGreaterElements(vector<int>& nums) {
        int N = nums.size();
        vector<int> res(N, -1);
        if(N < 2) return res;
        stack<int> st;
        st.push(0);
        //int bot = 0;
        for(int i=1; i<N*2; i++) {
            int num = nums[i%N];
            while(!st.empty() && nums[st.top()]<num) {
                res[st.top()] = num;
                st.pop();
            }
            //if(st.empty()) bot = i;
            if(i<N) st.push(i);
        }
        return res;
    }
or, change the upper bound for the loop when i>=N
    vector<int> nextGreaterElements(vector<int>& nums) {
        int N = nums.size();
        vector<int> res(N, -1);
        if(N < 2) return res;
        stack<int> st;
        st.push(0);
        int bot = 0;
        for(int i=1; i<N+bot+1; i++) {
            int num = nums[i%N];
            while(!st.empty() && nums[st.top()]<num) {
                res[st.top()] = num;
                st.pop();
            }
            if(st.empty()) bot = i;
            if(i<N) st.push(i);
        }
        return res;
    }

678. Valid Parenthesis String

Solution 1. Use stacks. Storing the index of each char.
    bool checkValidString(string s) {
        stack<int> st;
        stack<int> blk;
        for(int i=0; i<s.size(); i++) {
            char c = s[i];
            if(c == '(') st.push(i);
            else if(c == '*') blk.push(i);
            else {
                if(st.empty() && blk.empty()) return false;
                if(!st.empty()) st.pop();
                else blk.pop();
            }
        }
        if(st.size()>blk.size()) return false;
        while(!st.empty() && !blk.empty()) {
            if(blk.top()<st.top()) return false;
            st.pop();
            blk.pop();
        }
        return st.empty();
    }
Solution 2. Counting the remaining '(' at each step.
    bool check(string& s, int i=0, int cnt=0) {
        if(cnt < 0) return false;
        if(i==s.size()) return cnt == 0;
        if(s[i] == '(') return check(s, i+1, cnt+1);
        else if(s[i] == ')') return check(s, i+1, cnt-1);
        else return check(s, i+1, cnt)
            || check(s, i+1, cnt+1)
            || check(s, i+1, cnt-1);
    }
    bool checkValidString(string s) {
        return check(s);
    }

155. Min Stack

https://leetcode.com/problems/min-stack/description/
Solution 1. One stack
class MinStack {
    stack<int> dst;
    int mi = INT_MAX;
public:
    /** initialize your data structure here. */
    MinStack() {
     
    }
    void push(int x) {
        if(x <= mi) {
            dst.push(mi);
            mi = x;
        }
        dst.push(x);
    }
    void pop() {
        if(dst.top() == mi) {
            dst.pop();
            mi = dst.top();
        }
        dst.pop();
    }
 
    int top() {
        return dst.top();
    }
 
    int getMin() {
        return mi;
    }
};
or, push the min every time pushing a new element.
class MinStack {
    stack<int> dst;
    int mi = INT_MAX;
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    void push(int x) {
        dst.push(mi);
        if(x <= mi) mi = x;
        dst.push(x);
    }
    void pop() {
        dst.pop();
        mi = dst.top();
        dst.pop();
    }
    int top() {
        return dst.top();
    }
    int getMin() {
        return mi;
    }
Solution 2. Two stacks.
class MinStack {
    stack<int> dst;
    stack<int> mst;
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    void push(int x) {
        int mi;
        if(dst.empty()) mi = x;
        else mi = min(mst.top(), x);
        mst.push(mi);
        dst.push(x);
    }
    void pop() {
        dst.pop();
        mst.pop();
    }
    int top() {
        return dst.top();
    }
    int getMin() {
        return mst.top();
    }
};

225. Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/description/

class MyStack {
    queue<int> q;
public:
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
        for(int i=0; i<q.size()-1;i++) {
            q.push(q.front());
            q.pop();
        }
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }
    /** Get the top element. */
    int top() {
        return q.front();
    }
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};

20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

    bool isValid(string s) {
        if(s.size() == 0) return true;
        stack<char> st;
        for(char c : s){
            switch(c) {
                case '{': st.push(c); break;
                case '(': st.push(c); break;
                case '[': st.push(c); break;
                case '}':
                    if(st.empty()||st.top()!='{') return false;
                    else st.pop();
                    break;
                case ')':
                    if(st.empty()||st.top()!='(') return false;
                    else st.pop();
                    break;
                case ']':
                    if(st.empty()||st.top()!='[') return false;
                    else st.pop();
                    break;
            }
        }
        if(st.empty()) return true;
        else return false;
    }

112. Path Sum

https://leetcode.com/problems/path-sum/description/

Recursion
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && sum==root->val) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
or,
    bool preOrder(TreeNode* node, int sum, int s) {
        s += node->val;
        if(!node->left && !node->right && s==sum) return true;
        return (node->left? preOrder(node->left, sum, s):false) ||
        (node->right? preOrder(node->right, sum, s):false);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        return preOrder(root, sum, 0);
    }
Iteration
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        stack<TreeNode*> st;
        stack<int> sm;
        st.push(root);
        sm.push(0);
        TreeNode* node;
        int sn = 0;
        while(!st.empty()) {
            node = st.top();
            st.pop();
            sn = sm.top() + node->val;
            sm.pop();
            if(!node->left && !node->right && sn==sum) return true;
            if(node->right) {st.push(node->right); sm.push(sn);}
            if(node->left) {st.push(node->left); sm.push(sn);}
        }
        return false;
    }

232. Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/description/
Solution 1. Use 1 stack.  Recursively push x to the bottom of the stack.
    stack<int> st;
public:
    /** Initialize your data structure here. */
    MyQueue() {
     
    }
    /** Push element x to the back of queue. */
    void push(int x) {
        if(st.empty()) {
            st.push(x);
            return;
        }
        int y = st.top();
        st.pop();
        push(x);
        st.push(y);
    }
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x = st.top();
        st.pop();
        return x;
    }
    /** Get the front element. */
    int peek() {
        return st.top();
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return st.empty();
    }

};
Solution 2. Use 2 stacks for input and output, respectively. move from input to output stack only when output stack is empty.
class MyQueue {
    stack<int> sti;
    stack<int> sto;
public:
    /** Initialize your data structure here. */
    MyQueue() {
     
    }
    /** Push element x to the back of queue. */
    void push(int x) {
        sti.push(x);
    }
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        peek();
        int x = sto.top();
        sto.pop();
        return x;
    }
    /** Get the front element. */
    int peek() {
        if(sto.empty()) {
            while(!sti.empty()) {
                sto.push(sti.top());
                sti.pop();
            }
        }
        return sto.top();
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return sti.empty() && sto.empty();
    }
};

206. Reverse Linked List

Solution 1. Iterative method
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* node = head;
        while(node){
            head = node;
            node = node->next;
            head->next = prev;
            prev = head;
        }
        return head;

    }
Solution 2. Recursion
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return node;

    }
Solution 2. With the help of a stack
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> st;
        ListNode* node = head;
        while(node){
            st.push(node);
            node = node->next;
        }
        if(head) {
            head = st.top();
            node = head;
            st.pop();
        }
        while(!st.empty()) {
            node->next = st.top();
            st.pop();
            node = node->next;
        }
        if(node) node->next = nullptr;
        return head;
    }