動畫圖解“兩數(shù)相加”，小學(xué)生都能看懂
本文轉(zhuǎn)載自微信公眾號「程序員小熊」，作者Dine。轉(zhuǎn)載本文請聯(lián)系程序員小熊公眾號。
前言
大家好，我是來自于華為的程序員小熊。今天給大家?guī)硪坏栏骰ヂ?lián)網(wǎng)大廠面試中常考的涉及到鏈表相關(guān)的中檔題題，即力扣上的第 2 題-兩數(shù)相加。
本文主要介紹迭代+虛擬頭節(jié)點(diǎn)的策略來解答此題，供大家參考，希望對大家有所幫助。
兩數(shù)相加
給你兩個非空的鏈表，表示兩個非負(fù)的整數(shù)。
它們每位數(shù)字都是按照逆序的方式存儲的，并且每個節(jié)點(diǎn)只能存儲一位數(shù)字。
請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。
示例1
其它示例及提示
解題思路
由于題目已明確告知每個節(jié)點(diǎn)只能存儲一位數(shù)字，因此當(dāng)兩鏈表相同位置的數(shù)字之和大于 10 時，需要考慮進(jìn)位的問題。
例兩個鏈表：l1 = [3,4,3], l2 = [5,6,4]。
當(dāng)他們的第二個節(jié)點(diǎn)的數(shù)字相加時，需要進(jìn)位 1 到第三個節(jié)點(diǎn)的數(shù)字之和。
由于需要遍歷一遍兩個鏈表，所以考慮采用迭代的思想。
注意點(diǎn)
1.考慮中間位進(jìn)位的問題;
例如 l1 = [3,4,3], l2 = [5,6,4]。
2.考慮最高位進(jìn)位的問題。
例如 l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]。
舉栗
以 l1 = [3,4,3], l2 = [5,6,4] 為例子，如下圖示：
示例
不斷遍歷兩個鏈表，將相同位置的節(jié)點(diǎn)的數(shù)值相加，并更新到新的鏈表;
相同位置的節(jié)點(diǎn)的數(shù)值相加并更新
遇到需要進(jìn)位時，保留需要進(jìn)位的值;
需要進(jìn)位時，先保留進(jìn)位
將上次進(jìn)位的值與兩鏈表本次節(jié)點(diǎn)的和相加;
進(jìn)位更新
完整的處理過程，如下動圖示：
兩鏈表節(jié)點(diǎn)值相加更新到新鏈表，完整處理過程
Show me the Code
「C」
- struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
- struct ListNode *dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
- dummyHead->val = 0;
- dummyHead->next = NULL;
- struct ListNode *node = dummyHead;
- int carry = 0; // 進(jìn)位
- /* 遍歷兩個鏈表 */
- for (struct ListNode* p = l1, *q = l2; p != NULL || q != NULL;) {
- /* 相同位置節(jié)點(diǎn)值之和 */
- int sum = carry;
- sum += (p != NULL) ? p->val : 0;
- sum += (q != NULL) ? q->val : 0;
- /* 將兩鏈表相同位置的和的值，不斷更新到新的鏈表 */
- node->next = (struct ListNode*)malloc(sizeof(struct ListNode));
- node = node->next;
- node->val = sum % 10;
- node->next = NULL;
- /* 進(jìn)位處理，兩鏈表不斷遍歷 */
- carry = sum / 10;
- p = (p == NULL) ? p : p->next;
- q = (q == NULL) ? q : q->next;
- }
- /* 最高位之和如果大于 10，增加一位，新鏈表的節(jié)點(diǎn)值為 1 */
- if(carry != 0) {
- node->next = (struct ListNode*)malloc(sizeof(struct ListNode));
- node = node->next;
- node->val = 1;
- node->next = NULL;
- }
- return dummyHead->next;
- }
「C++」
- ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
- ListNode* dummyHead = new ListNode(0);
- ListNode* node = dummyHead;
- int carry = 0;
- for (ListNode* p = l1, *q = l2; p != nullptr || q != nullptr;) {
- int sum = carry;
- sum += (p == nullptr) ? 0 : p->val;
- sum += (q == nullptr) ? 0 : q->val;
- node->next = new ListNode(sum % 10);
- node = node->next;
- carry = sum / 10;
- p = (p == nullptr) ? p : p->next;
- q = (q == nullptr) ? q : q->next;
- }
- if (carry != 0) {
- node->next = new ListNode(carry);
- }
- return dummyHead->next;
- }
「Java」
- ListNode addTwoNumbers(ListNode l1, ListNode l2) {
- ListNode dummyHead = new ListNode(-1);
- ListNode cur = dummyHead;
- int carry = 0;
- while (l1 != null || l2 != null) {
- int sum = carry;
- sum += (l1 == null) ? 0 : l1.val;
- sum += (l2 == null) ? 0 : l2.val;
- cur.next = new ListNode(sum % 10);
- cur = cur.next;
- carry = sum / 10;
- l1 = (l1 == null) ? l1 : l1.next;
- l2 = (l2 == null) ? l2 : l2.next;
- }
- if (carry != 0) {
- cur.next = new ListNode(carry);
- }
- return dummyHead.next;
- }
「Python3」
- def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
- dummyHead = ListNode(0)
- node = dummyHead
- carry = 0
- while(l1 or l2):
- sum = carry
- if(l1):
- sum += l1.val
- l1 = l1.next
- if l2:
- sum += l2.val
- l2 = l2.next
- node.next = ListNode(sum % 10)
- node = node.next
- carry = sum//10
- if carry != 0:
- node.next = ListNode(carry)
- return dummyHead.next
「Golang」
- func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
- dummy := new(ListNode)
- node := dummy
- carry := 0
- for l1 != nil || l2 != nil {
- sum := carry
- if l1 != nil {
- sum += l1.Val
- l1 = l1.Next
- }
- if l2 != nil {
- sum += l2.Val
- l2 = l2.Next
- }
- node.Next = new(ListNode)
- node = node.Next
- node.Val = sum % 10
- carry = sum / 10
- }
- if carry != 0 {
- node.Next = &ListNode{Val: carry}
- }
- return dummy.Next
- }
復(fù)雜度分析
時間復(fù)雜度：O(max(m, n))，其中 m 和 n 分別為兩個鏈表的長度，需要遞歸調(diào)用兩個鏈表的每個節(jié)點(diǎn)一次。
空間復(fù)雜度：O(1)，未開辟額外存儲空間。
