[[420833]]

本文轉(zhuǎn)載自微信公眾號「程序員小熊」，作者Dine。轉(zhuǎn)載本文請聯(lián)系程序員小熊公眾號。

前言

大家好，我是來自于華為的程序員小熊。今天給大家?guī)硪坏栏骰ヂ?lián)網(wǎng)大廠面試中?？嫉纳婕暗芥湵硐嚓P(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)，未開辟額外存儲空間。