题解 | #链表相加(二)#

栈的应用

/**
 * 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) {
        ListNode* a = head1, *b = head2, *s = NULL;
        ListNode* head = (ListNode*)malloc(sizeof(ListNode));
        head->next = head1;
        stack<ListNode*> ask, bsk, t;
        while (a != NULL) {
            ask.push(a);
            a = a->next;
        }

        while (b != NULL) {
            bsk.push(b);
            b = b->next;
        }

        if (bsk.size() > ask.size()) {
            t = bsk;
            bsk = ask;
            ask = t;
            head->next = head2;
        }
        int p = 0, sum = 0;
        while (!ask.empty() && !bsk.empty()) {
            a = ask.top();
            ask.pop();
            b = bsk.top();
            bsk.pop();
            sum = (a->val + b->val + p);
            a->val = sum % 10;
            p = sum / 10;
        }
        while (!ask.empty()) {
            a = ask.top();
            ask.pop();
            sum = a->val + p;
            a->val = sum % 10;
            p = sum / 10;
        }
        if (p != 0) {
            s = (ListNode*)malloc(sizeof(ListNode));
            s->val = p;
            s->next = head->next;
            head->next = s;
        }
        return head->next;
    }
};