leetcode兩數相加問題及其拓展問題解決
給出兩個非空 的連結串列用來表示兩個非負的整數。其中,它們各自的位數是按照逆序 的方式儲存的,並且它們的每個節點只能儲存一位 數字。
如果,我們將這兩個數相加起來,則會返回一個新的連結串列來表示它們的和。
您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。
示例:
輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出:7 -> 0 -> 8 原因:342 + 465 = 807複製程式碼
虛擬碼如下:
- 將當前結點初始化為返回列表的啞結點。
- 將進位carry初始化為0。
- 將p和q分別初始化為列表l1 和l2 的頭部。
-
遍歷列表l1 和l2 直至到達它們的尾端。
- 將x 設為結點p 的值。如果p 已經到達l1 的末尾,則將其值設定為0
- 將y 設為結點q 的值。如果q 已經到達l2 的末尾,則將其值設定為0
- 設定sum = x + y + carry。
- 更新進位的值,carry=sum/10。
- 建立一個數值為(sum mod 10)的新結點,並將其設定為當前結點的下一個結點,然後將當前結點前進到下一個結點。
- 同時,將p 和q 前進到下一個結點。
- 檢查carry=1 是否成立,如果成立,則向返回列表追加一個含有數字1 的新結點。
- 返回啞結點的下一個結點。
請注意,我們使用啞結點來簡化程式碼。如果沒有啞結點,則必須編寫額外的條件語句來初始化表頭的值。
請特別注意以下情況:
測試用例 | 說明 |
---|---|
l1=[0,1] l1=[0,1]l2=[0,1,2] l2=[0,1,2] |
當一個列表比另一個列表長時。 |
l1=[] l1=[]l2=[0,1] l2=[0,1] |
當一個列表為空時,即出現空列表。 |
l1=[9,9] l1=[9,9]l2=[1] l2=[1] |
求和運算最後可能出現額外的進位,這一點很容易被遺忘 |
複雜度分析
-
時間複雜度:O(max(m,n)),假設m 和n 分別表示l1 和l2 的長度,上面的演算法最多重複max(m,n) 次。
-
空間複雜度:O(max(m,n)), 新列表的長度最多為max(m,n)+1。
拓展
如果連結串列中的數字不是按逆序儲存的呢?例如:
(3 \to 4 \to 2) + (4 \to 6 \to 5) = 8 \to 0 \to 7
(3→4→2)+(4→6→5)=8→0→7
這種情況下:
解法一:
我們可以利用棧來儲存所有的元素,然後利用棧的後進先出的特點就可以從後往前取數字了,我們首先遍歷兩個連結串列,將所有數字分別壓入兩個棧s1和s2中,我們建立一個值為0的res節點,然後開始迴圈,如果棧不為空,則將棧頂數字加入sum中,然後將res節點值賦為sum%10,然後新建一個進位節點head,賦值為sum/10,如果沒有進位,那麼就是0,然後我們head後面連上res,將res指向head,這樣迴圈退出後,我們只要看res的值是否為0,為0返回res->next,不為0則返回res即可,參見程式碼如下:
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> s1, s2; while (l1) { s1.push(l1->val); l1 = l1->next; } while (l2) { s2.push(l2->val); l2 = l2->next; } int sum = 0; ListNode *res = new ListNode(0); while (!s1.empty() || !s2.empty()) { if (!s1.empty()) {sum += s1.top(); s1.pop();} if (!s2.empty()) {sum += s2.top(); s2.pop();} res->val = sum % 10; ListNode *head = new ListNode(sum / 10); head->next = res; res = head; sum /= 10; } return res->val == 0 ? res->next : res; } }; 複製程式碼
解法二:
我們首先統計出兩個連結串列長度,然後根據長度來呼叫遞迴函式,需要傳一個引數差值,遞迴函式引數中的l1連結串列長度長於l2,在遞迴函式中,我們建立一個節點res,如果差值不為0,節點值為l1的值,如果為0,那麼就是l1和l2的和,然後在根據差值分別呼叫遞迴函式求出節點post,然後要處理進位,如果post的值大於9,那麼對10取餘,且res的值自增1,然後把pos連到res後面,返回res,最後回到原函式中,我們仍要處理進位情況,參見程式碼如下:
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int n1 = getLength(l1), n2 = getLength(l2); ListNode *head = new ListNode(1); head->next = (n1 > n2) ? helper(l1, l2, n1 - n2) : helper(l2, l1, n2 - n1); if (head->next->val > 9) { head->next->val %= 10; return head; } return head->next; } int getLength(ListNode* head) { int cnt = 0; while (head) { ++cnt; head = head->next; } return cnt; } ListNode* helper(ListNode* l1, ListNode* l2, int diff) { if (!l1) return NULL; ListNode *res = (diff == 0) ? new ListNode(l1->val + l2->val) : new ListNode(l1->val); ListNode *post = (diff == 0) ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, diff - 1); if (post && post->val > 9) { post->val %= 10; ++res->val; } res->next = post; return res; } }; 複製程式碼
解法三:
先算出兩個連結串列的長度,我們把其中較長的放在l1,然後我們算出兩個連結串列長度差diff。如果diff大於0,我們用l1的值新建節點,並連在cur節點後(cur節點初始化時指向dummy節點)。並且如果l1的值不等於9,那麼right節點也指向這個新建的節點,然後cur和l1都分別後移一位,diff自減1。當diff為0後,我們迴圈遍歷,將此時l1和l2的值加起來放入變數val中,如果val大於9,那麼val對10取餘,right節點自增1,將right後面節點全賦值為0。在cur節點後新建節點,節點值為更新後的val,如果val的值不等於9,那麼right節點也指向這個新建的節點,然後cur,l1和l2都分別後移一位。最後我們看dummy節點值若為1,返回dummy節點,如果是0,則返回dummy的下一個節點。
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int n1 = getLength(l1), n2 = getLength(l2), diff = abs(n1 - n2); if (n1 < n2) swap(l1, l2); ListNode *dummy = new ListNode(0), *cur = dummy, *right = cur; while (diff > 0) { cur->next = new ListNode(l1->val); if (l1->val != 9) right = cur->next; cur = cur->next; l1 = l1->next; --diff; } while (l1) { int val = l1->val + l2->val; if (val > 9) { val %= 10; ++right->val; while (right->next) { right->next->val = 0; right = right->next; } right = cur; } cur->next = new ListNode(val); if (val != 9) right = cur->next; cur = cur->next; l1 = l1->next; l2 = l2->next; } return (dummy->val == 1) ? dummy : dummy->next; } int getLength(ListNode* head) { int cnt = 0; while (head) { ++cnt; head = head->next; } return cnt; } };複製程式碼
參考資料:
discuss.leetcode.com/topic/67076…
discuss.leetcode.com/topic/65279…