兩數(shù)相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order 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.

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

大致意思：給定兩個(gè)非空的鏈表代表兩個(gè)非負(fù)整數(shù)，數(shù)字在鏈表中以倒序存儲(chǔ)（意思就是好比如存儲(chǔ)整數(shù)342，在鏈表中是2->4->3），鏈表中的每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)數(shù)字。計(jì)算兩個(gè)數(shù)字的和并以鏈表的形式返回。

約定兩個(gè)數(shù)字不包含頭部0的數(shù)字，除了0他本身。

常規(guī)解法：首先依次遍歷兩個(gè)鏈表，找到最長(zhǎng)的那個(gè)鏈表作為主鏈表，每次遍歷鏈表中的元素進(jìn)行相加結(jié)果覆蓋住鏈表中的值，最后短的鏈表遍歷完后檢查進(jìn)位情況看是否在主鏈表中添加新的結(jié)點(diǎn)。這種方法比較通俗易懂，但是時(shí)間復(fù)雜度特別高。

/**
 * 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 *head=retLongList(l1,l2);
        ListNode *one=head;
        ListNode *two=NULL;
        if(one==l1)
        {
            two=l2;
        }
        else
        {
            two=l1;
        }
        int zv=0;
        while(one!=NULL && two!=NULL)
        {
            zv=(one->val+two->val)/10;
            one->val+=two->val;
            ListNode* fir=one;
            ListNode* sec=two;
            while(zv>0)
            {
                fir->val%=10;
                if(fir->next==NULL)
                {
                    fir->next=new ListNode(1);
                    fir->next->val=0;
                    fir->next->next=NULL;
                }
                fir->next->val+=zv;
                zv=fir->next->val/10;
                fir=fir->next;
            }
            one=one->next;
            two=two->next;
        }
        return head;
    }
    ListNode* retLongList(ListNode* l1, ListNode* l2)
    {
        ListNode* first=l1;
        ListNode* second=l2;
        while(1)
        {
            if(l1->next==NULL && l2->next==NULL)
            {
                return first;
            }
            else if(l1->next==NULL && l2->next!=NULL)
            {
                return second;
            }
            else if(l1->next!=NULL && l2->next==NULL)
            {
                return first;
            }
            else
            {
                l1=l1->next;
                l2=l2->next;
            }
        }
    }
};

其他解法：分別遍歷兩個(gè)鏈表，用一個(gè)變量表示是否有進(jìn)位。某一個(gè)鏈表遍歷完后，再將另一個(gè)鏈表沒遍歷完的連接在結(jié)果鏈表之后，如果最后有進(jìn)位需要添加一個(gè)結(jié)點(diǎn)。時(shí)間復(fù)雜度較低。

class Solution {  
public:  
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
        int carry = 0;  
        ListNode* tail = new ListNode(0);  
        ListNode* ptr = tail;  
        while(l1 != NULL || l2 != NULL){  
            int val1 = 0;  
            if(l1 != NULL){  
                val1 = l1->val;  
                l1 = l1->next;  
            }    
            int val2 = 0;  
            if(l2 != NULL){  
                val2 = l2->val;  
                l2 = l2->next;  
            }       
            int tmp = val1 + val2 + carry;  
            ptr->next = new ListNode(tmp % 10);  
            carry = tmp / 10;  
            ptr = ptr->next;  
        }  
        if(carry == 1){  
            ptr->next = new ListNode(1);  
        }  
        return tail->next;  
    }  
};