LeetCode_2_Add Two Numbers

題目描述：

給出兩個 非空 的連結清單用來表示兩個非負的整數。其中，它們各自的位數是按照 逆序 的方式存儲的，并且它們的每個節點隻能存儲 一位 數字。如果，我們将這兩個數相加起來，則會傳回一個新的連結清單來表示它們的和。您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

輸入樣例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807      

算法思想：将兩條連結清單從頭到尾進行周遊，将指針目前所指的節點中的數和進位相加并取餘，得到個位數。定義一個進位變量carry，用于标記進位。最後将生成的連結清單傳回即可。

ListNode *head=NULL,*p=NULL;
        int carry=0;
        while(l1||l2){
            int sum1=l1?l1->val:0;
            int sum2=l2?l2->val:0;
            int sum=sum1+sum2+carry;
            carry=sum/10;
            ListNode *cur=new ListNode(sum%10);
            if(!head)
                head=cur;
            if(p)
                p->next=cur;
            p=cur;
            l1=l1?l1->next:NULL;
            l2=l2?l2->next:NULL;
        }
        if(carry){
            ListNode *l=new ListNode(carry);
            p->next=l;
        }
        return head;      

以下是運作時間效率圖

題外話：很長時間沒有寫連結清單的算法題目了，手法有點生疏。以下是剛開始寫的有點小bug的程式段

ListNode *l3,*p;
        ListNode *head=new ListNode(0); 
        p=l3=head;
        int carry=0;
        while((l1!=NULL)&&(l2!=NULL)){
            int sum=0;
            sum=l1->val+l2->val+carry;
            carry=sum/10;
            sum%=10;
            ListNode* tempNode=new ListNode(sum);
            l3->next=tempNode;
            l3=l3->next;
            l1=l1->next;
            l2=l2->next;
        }
        while(l1!=NULL){
            ListNode* tempNode=new ListNode(l1->val);
            l3->next=tempNode;
            l1=l1->next;
            l3=l3->next;
        }
        while(l2!=NULL){
            ListNode* tempNode=new ListNode(l2->val);
            l3->next=tempNode;
            l2=l2->next;
            l3=l3->next;
        }
        if(carry!=0){
            ListNode* tempNode=new ListNode(carry);
            l3->next=tempNode;
            l3=l3->next;
        }
        head=head->next;
        delete p;
        return head;      

網上大神的程式設計：

此算法思想：以l1作為結果連結清單，最後傳回的就是l1的這條連結清單。将l2中的資料依次加到l1對應的節點上，如果相加後l1->val的值>=10，則說明産生了進位，如果l1->nextNULL，則需要申請節點來存儲進位結果，不空則将進位加到next中的val即可。當l1NULL時，隻需要将l2剩餘的節點連接配接到l1上即可。

此算法節省了很多時間，而且也節省了很多空間(不需要申請無用的節點了)

class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    auto l3=l1;
    while(1) {
      if (l1==NULL) {
        return l3;
      }
      if(l2!=NULL) {
        l1->val+=l2->val;
        l2=l2->next;
      }
      if (l1->val>=10) {
        l1->val-=10;
        if (l1->next==NULL) {
          l1->next = new ListNode(1);
        }else {
          l1->next->val++;
        }
      }
      if (l1->next==NULL&&l2!=NULL) {
        l1->next=l2;
        l2=NULL;
      }
      l1=l1->next;
    }
  }
};