题目描述

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

样例

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

反转链表 或 使用栈代替反转链表

算法1

反转链表

加法必须从最低位开始，所以我们可以首先反转两个链表，然后从最低位开始加起来，最后将结果再反转一次得到答案。

C++ 代码

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //反转链表1
        ListNode* pre = NULL;
        ListNode* cur = l1;
        while(cur != NULL)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        l1 = pre;
        //反转链表2
        pre = NULL;
        cur = l2;
        while(cur != NULL)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        l2 = pre;
        //进行加法运算
        int cn = 0;
        ListNode* dummy = new ListNode(0);
        cur = dummy;
        while(l1 || l2)
        {
            int x, y;
            x = (l1 == NULL)?0:l1->val;
            y = (l2 == NULL)?0:l2->val;
            cur->next = new ListNode((x + y + cn) % 10);
            cn = (x + y + cn) / 10;
            if(l1 != NULL) l1 = l1->next;
            if(l2 != NULL) l2 = l2->next;
            cur = cur->next;
        }
        if(cn == 1)
            cur->next = new ListNode(1);
        //再反转一次结果链表
        pre = NULL;
        cur = dummy->next;
        while(cur != NULL)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre; 
    }

算法2

使用栈代替反转链表

C++ 代码

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> st1,st2,res;
        while(l1){st1.push(l1->val); l1 = l1->next;}
        while(l2){st2.push(l2->val); l2 = l2->next;}
        int cn = 0;
        while(!st1.empty()||!st2.empty())
        {
            int x,y;
            x = st1.empty()?0:st1.top();
            y = st2.empty()?0:st2.top();
            res.push((x + y + cn) % 10);
            cn = (x + y + cn) / 10;
            if(!st1.empty())st1.pop();
            if(!st2.empty())st2.pop();
        }
        if(cn == 1)
            res.push(1);
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(!res.empty())
        {
            cur->next = new ListNode(res.top());
            res.pop();
            cur = cur->next;
        }
        return dummy->next;
    }