兩數(shù)相加

我們來看看題目，，，，
往往困難的題只需要 簡單的敘述。

好像只用找到兩個數(shù)，整合成一個鏈表就可以。應(yīng)該

1 思路一 （暴斃版）

1. 首先 我最快想到思路是 分別根據(jù)兩個鏈表求出對應(yīng)數(shù)
2. 然后加一起 ，得到和
3. 再把和拆分儲存到鏈表里
   為此我們需要手撕一下鏈表頭插。

 typedef struct ListNode SLTNode;
SLTNode* buynode(int n) {
	//開辟空間
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    node->next = NULL;
    node->val = n;
    return node;
}
void pushback(SLTNode** ret, int n) {
	//創(chuàng)建節(jié)點
    SLTNode* node = buynode(n);
    //如果頭為空 node成為頭
    if (*ret == NULL)
    {
        *ret = node;
        return;
    }
	//找尾
    SLTNode* cur = *ret;
    while(cur->next) {
        cur = cur->next;
    }
    //插入
    cur->next = node;
    return;
}

SLTNode* addTwoNumbers(SLTNode* l1, SLTNode* l2) {
    //選擇long long 來儲存較大數(shù)
    long long  num1 = 0, num2 = 0;
    long long   a = 1;
    //計算數(shù)一
    while (l1 != NULL) {
        num1 += (l1->val) * a;
        l1 = l1->next;
        a *= 10;
    }
    a = 1;
    //計算數(shù)二
    while (l2 != NULL) {
        num2 += (l2->val) * a;
        l2 = l2->next;
        a *= 10;
    }
    //求和
    long long  sum = num1 + num2;
    //構(gòu)建鏈表
    SLTNode* ret = NULL;
    if(sum == 0)
    {
        pushback(&ret,0);
        return ret;
    }
    while (sum != 0) {
        long long  n = sum % 10;
        pushback(&ret, n);
        sum = sum / 10;
    }
    //返回鏈表
    return ret;
}

一頓操作猛如虎，一看提交原地杵········

雖然我已經(jīng)使用最大的數(shù)據(jù)類型 long long ,但是最后的測試數(shù)據(jù)太大了，還有3 個樣例無法通過。這下子要從頭開始了。
（這就得夸夸力扣了，豐富的測試用例，不會隨便讓你過）

2 思路二 （本質(zhì)出發(fā)）

思路一的簡單加和不能完成目的，那我們只好深入到加法的本質(zhì)中去：
按位計算，滿10進一 ,逐個逐個計算
這樣就算把天文數(shù)字填進來，只要內(nèi)存夠，咱都能解決!!!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Listnode;
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    //創(chuàng)建頭結(jié)點
    Listnode* head = (Listnode*)malloc(sizeof(Listnode));
    //創(chuàng)建尾指針
    Listnode* cur = head;
    //進位數(shù)
    int t = 0;
    //l1 l2 t 全為空才停止
    while(l1||l2||t){
        //l1 為真則把值賦值在t上
        if(l1) {
            t += l1->val;
            l1 = l1->next;
        }
        //l2 為真則把值賦值在t上
        if(l2) {
            t += l2->val;
            l2 = l2->next;
        }
        //創(chuàng)建節(jié)點
        cur->next = ( Listnode *)malloc(sizeof(Listnode));
        cur->next->val = t % 10;
        cur->next->next = NULL;
        //向后移動
        cur = cur->next;
        t /= 10;
    }
    return head->next;

}

一氣呵成，呼~~~~
我們舍去手撕鏈表頭插的痛苦。直接改為“滿足條件”就開辟新空間。因此為了方便這里使用帶頭鏈表。
提交！ 過過過過啦！?。。。。?/strong>

來看看性能怎么樣，打敗了80%的用戶，10ms.
來分析一下咱們算法的時間復(fù)雜度 ，遍歷鏈表，最壞情況也是遍歷了一條很長的鏈表。那咱時間復(fù)雜度就是O(n)。
?。窟€有比 O(n) 更快的算法？？？