Leetcode--Add Two Numbers(0002)

轉載請註明：http://www.cnblogs.com/igoslly/p/8672467.html

來看一下題目：

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路：

        1、由於兩個數的大小位數，鏈表 -> int數進行的想法基本無望，可能越界

        2、鏈表已經逆序，已經提供很好的“對應位相加，向前進位”的運算模式

註意點：

        1、List1和List2不等長

        2、當某個List完成後，可單個計算另外的List

        3、考慮進位關係，例如9+99999

        4、最後進位時，需額外設定val=1的結點

實現方法1（初始）：

       方法1即是依照上面思路，依樣畫葫蘆得到的結果

       但其實細看，本題代碼重覆的部分太多，而且一直需要使用pre變數跟蹤前結點，有些多餘

/**
 * 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 *p1=l1,*p2=l2,*pre=p1;
        int up=0;
        
        // 將結點l1作為結果鏈表返回，在l1和l2均在有效範圍內，進行添加，同時更新up進位
        while(p1&&p2){
            p1->val+=p2->val+up;
            up=p1->val/10;
            if(up==1){
                p1->val-=10;
            }
            pre=p1;
            p1=p1->next;
            p2=p2->next;
        }
        
        // 當l1結束後，pre最後個元素連接到l2後部
        if(p1==NULL){
            pre->next=p2;
            while(p2!=NULL){
                p2->val+=up;
                up=p2->val/10;
                if(up==1){
                    p2->val-=10;
                }
                pre=p2;
                p2=p2->next;
            }
        }
        
        // 當l2結束後，單獨計算l1
        if(p2==NULL){
            while(p1!=NULL){
                p1->val+=up;
                up=p1->val/10;
                if(up==1){
                    p1->val-=10;
                }
                pre=p1;
                p1=p1->next;
            }
        }
        
        // 當計算結束，up=1時，表示和多一位，新創建val=1的ListNode添加
        if(up==1){
            pre->next=new ListNode(1);
        }
        return l1;
    }
};

實現方法2 （對方法1進行優化）：

            相對看起來更加簡潔

/**
 * 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) {  
        int carry=0;
        ListNode* listNode=new ListNode(0);
        ListNode* p1=l1,*p2=l2,*p3=listNode;
        
        // 修改判斷條件從 && 到 ||
        while(p1!=NULL||p2!=NULL)
        {   
            // 在while迴圈里添加p1和p2的判斷，省去了某個List完畢後單獨List的情況
            if(p1!=NULL)
            {
                carry+=p1->val;
                p1=p1->next;
            }
            if(p2!=NULL)
            {
                carry+=p2->val;
                p2=p2->next;
            }
            p3->next=new ListNode(carry%10);
            p3=p3->next;
            carry/=10;
        }
        
        // 由於闢出了單獨的result鏈表，故而無需再用pre繼續前結點
        if(carry==1)
            p3->next=new ListNode(1);
        return listNode->next;  
    }
};