题解 | #双栈+头插法——链表相加(二)#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/*两个栈分别存储两个链表的结点，利用先进后出特性进行尾加，将加的值分成进位和个位，个位利用头插法放入新链表*/
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<int> s1;
        stack<int> s2;
        ListNode *temp = head1;
        while(temp){
            s1.push(temp->val);
            temp = temp->next;
        }
        temp = head2;
        while(temp){
            s2.push(temp->val);
            temp = temp->next;
        }

        ListNode *ymm = new ListNode(-1);
        int flag = 0; //进位
        while(!s1.empty() || !s2.empty()){
            int a = 0;
            int b = 0;
            if(!s1.empty()){
                a = s1.top();
                s1.pop();
            }
            if(!s2.empty()){
                b = s2.top();
                s2.pop();
            }
            int sum = a + b + flag;
            int ans = sum % 10;
            flag = sum / 10;
            ListNode *p = new ListNode(ans);
            p->next = ymm->next;
            ymm->next = p;
        }
        if(flag != 0) {
             ListNode *p = new ListNode(flag);
             p->next = ymm->next;
             ymm->next = p;
        }
        return ymm->next;
    }
};