/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode* first = l1;

        ListNode* second = l2;

        int result1=,result2=;

        long long result=;

        stack<int> S;

        int count=;

        while(l1 != NULL){

            S.push(l1->val);

            l1 = l1->next;

        }

        count = S.size()-;

        while(!S.empty()){

            result1 += pow(,count--) * S.top();

            S.pop();

        }

        while(l2 != NULL){

            S.push(l2->val);

            l2 = l2->next;

        }

        count = S.size()-;

        while(!S.empty()){

            result2 += pow(,count--) * S.top();

            S.pop();

        }

        result = result1 + result2;

        delete first,second;

        // ListNode*p = new ListNode(-1);  //头节点

        ListNode* pHead = NULL;

        ListNode* p = pHead;

        if(!result){

            ListNode* q = new ListNode();

            pHead = q;

        }

        while(result){

            int val = result % ;

            result /= ;

            ListNode* q = new ListNode(val);

            if(pHead == NULL){

                pHead = q;

                p = q;

            }

            else{

                p->next = q;

                p = p->next;

            }

        }

        return pHead;

    }

};

此方法会溢出，超过long long 型范围

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {   //正确解法，按位相加，注意进位

    ListNode *head = NULL, *prev = NULL;

    int carry = ;

    while (l1 || l2) {

        int v1 = l1? l1->val: ;

        int v2 = l2? l2->val: ;

        int tmp = v1 + v2 + carry;

        carry = tmp / ;

        int val = tmp % ;

        ListNode* cur = new ListNode(val);

        if (!head) head = cur;

        if (prev) prev->next = cur;

        prev = cur;

        l1 = l1? l1->next: NULL;

        l2 = l2? l2->next: NULL;

    }

    if (carry > ) {

        ListNode* l = new ListNode(carry);

        prev->next = l;

    }

    return head;

}

int lengthOfLongestSubstring(string s) {

    int maxLength = ;

    int count;

    for(int i=;i<s.length();i++){

        string currString = "";

        count = ;

        for(int j=i;j<s.length();j++){

            if(currString.find(s[j])>=currString.length()){

                currString += s[j];

                count++;

                cout<<s[j]<<endl;

                cout<<"string:"<<currString<<endl;

                if(count>maxLength) maxLength = count;

            }

            else{

                break;

            }

        }

    }

    return maxLength;

}

string longestPalindrome(string s) {

    string maxString = "";

    int maxLength = ;

    int count = ;

    for(int i=;i<s.length();i++){

        string Str = "";

        int index = s.rfind(s[i]);

        int start = i;

        int end = index;

        int count = ;

        int ii=start;

        while(ii<=index){

            if(s[ii]==s[index]){ii++;index--;}

            else{

                ii = start;

                index = end-;

                end--;

            }   //匹配失败

        }

        if(ii>index){  //匹配成功

            for(int k=start;k<=end;k++)

                Str += s[k];

            count = Str.length();

        }

        if(count>=maxLength) {maxString = Str;maxLength=count;}

    }

    return maxString;

}

int myAtoi(string str) {

    long result = ;

    int indicator = ;

    for(int i = ; i<str.size();)

    {

        i = str.find_first_not_of(' ');

        if(str[i] == '-' || str[i] == '+')

            indicator = (str[i++] == '-')? - : ;

        while(''<= str[i] && str[i] <= '')

        {

            result = result* + (str[i++]-'');

            if(result*indicator >= INT_MAX) return INT_MAX;

            if(result*indicator <= INT_MIN) return INT_MIN;

        }

        return result*indicator;

    }

    return ;

}

    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> res;

        int sum;

        sort(nums.begin(),nums.end());

        for(int i=;i<nums.size();i++){

            if(i> && nums[i]==nums[i-])

                continue;

            int l=i+;

            int r=nums.size()-;

            while(l<r){

                sum = nums[i]+nums[l]+nums[r];

                if(sum<) l++;

                else if(sum>) r--;

                else{

                    res.push_back(vector<int>{nums[i],nums[l],nums[r]});

                    while(nums[l]==nums[l+]) l++;   //去除重复

                    while(nums[r]==nums[r-]) r--;

                    l++;

                    r--;

                }

            }

        }

        return res;

    }

    int maxArea(vector<int>& height) {

        int maxAreas=;

        int currAreas=;

        for(int i=;i<height.size();i++){

            for(int j=i+;j<height.size();j++){

                currAreas = (j-i)*min(height[i],height[j]);

                if(currAreas>maxAreas) maxAreas = currAreas;

            }

        }

        return maxAreas;

    }

    string intToRoman(int num) {

        const string THOUS[]={"","M","MM","MMM"};

        const string HUNDS[]=              {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};

        const string TENS[]={"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};

        const string ONES[]={"","I","II","III","IV","V","VI","VII","VIII","IX"};

        string result = "";

        result += THOUS[num/]; num %= ;

        result += HUNDS[num/]; num %= ;

        result += TENS[num/]; num %= ;

        result += ONES[num%];

        return result;

    }

    int threeSumClosest(vector<int>& nums, int target) {

        sort(nums.begin(),nums.end());

        int minDist=INT_MAX;

        int res=;

        for(int i=;i<nums.size();i++){

            int l=i+;

            int r=nums.size()-;

            while(l<r){

                int sum = nums[i]+nums[r]+nums[l];

                if(sum==target) return sum;

                if(abs(sum-target)<minDist) {res=sum;minDist=abs(sum-target);}

                if(sum>target) r--;

                else l++;

            }//while

        }

        return res;

    }

};

    vector<string> letterCombinations(string digits) {

        if(digits.empty()) return vector<string>();

        vector<string> result;

        result.push_back("");

        vector<string> src = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        for(int i=;i<digits.size();i++){

            int num = digits[i]-'';

            if(num< || num>) break;

            const string& candidate = src[num];

            if(candidate.empty()) continue;

            vector<string> tmp;

            for(int j=;j<candidate.size();j++){

                for(int k=;k<result.size();k++)

                    tmp.push_back(result[k]+candidate[j]);

            }

            result.swap(tmp);

        }

        return  result;

    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {

        if(head == NULL) return NULL;

        ListNode* after=head;

        ListNode* befor=head;

        ListNode* toBeDelete;

        for(int i=;i<n;i++){

            befor = befor->next;

            if(befor==NULL) return head->next;

        }

        while(befor->next!=NULL){

            befor = befor->next;

            after = after->next;

        }

        toBeDelete = after->next;

        after->next = toBeDelete->next;

        delete toBeDelete;

        toBeDelete = NULL;

        return head;

    }

    vector<string> res;

    void helper(string str,int left,int right){

        if(left== && right==) res.push_back(str);

        if(left!=) helper(str+'(',left-,right);

        if(right!= && right>left) helper(str+')',left,right-);

    }

    vector<string> generateParenthesis(int n) {

        helper("",n,n);

        return res;

    }

    ListNode* swapPairs(ListNode* head) {

        if(head==NULL) return NULL;

        ListNode tmp();

        ListNode* curr=head;

        ListNode* pre=&tmp;

        tmp.next=head;

        while(curr && curr->next){

            pre->next=curr->next;

            pre=pre->next;

            curr->next=pre->next;

            pre->next=curr;

            pre=curr;

            curr=curr->next;

        }

        return tmp.next;

    }