[[420833]]

本文轉載自微信公眾號「程序員小熊」，作者Dine。轉載本文請聯系程序員小熊公眾號。

前言

大家好，我是來自于華為的程序員小熊。今天給大家帶來一道各互聯網大廠面試中常考的涉及到鏈表相關的中檔題題，即力扣上的第 2 題-兩數相加。

本文主要介紹迭代+虛擬頭節點的策略來解答此題，供大家參考，希望對大家有所幫助。

兩數相加

給你兩個非空的鏈表，表示兩個非負的整數。

它們每位數字都是按照逆序的方式存儲的，并且每個節點只能存儲一位數字。

請你將兩個數相加，并以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例1

其它示例及提示

解題思路

由于題目已明確告知每個節點只能存儲一位數字，因此當兩鏈表相同位置的數字之和大于 10 時，需要考慮進位的問題。

例兩個鏈表：l1 = [3,4,3], l2 = [5,6,4]。

當他們的第二個節點的數字相加時，需要進位 1 到第三個節點的數字之和。

由于需要遍歷一遍兩個鏈表，所以考慮采用迭代的思想。

注意點

1.考慮中間位進位的問題;

例如 l1 = [3,4,3], l2 = [5,6,4]。

2.考慮最高位進位的問題。

例如 l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]。

舉栗

以 l1 = [3,4,3], l2 = [5,6,4] 為例子，如下圖示：

示例

不斷遍歷兩個鏈表，將相同位置的節點的數值相加，并更新到新的鏈表;

相同位置的節點的數值相加并更新

遇到需要進位時，保留需要進位的值;

需要進位時，先保留進位

將上次進位的值與兩鏈表本次節點的和相加;

進位更新

完整的處理過程，如下動圖示：

兩鏈表節點值相加更新到新鏈表，完整處理過程

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;  //  進位 
 
    /* 遍歷兩個鏈表 */ 
    for (struct ListNode* p = l1, *q = l2; p != NULL || q != NULL;) { 
        /* 相同位置節點值之和 */ 
        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; 
 
        /* 進位處理，兩鏈表不斷遍歷 */ 
        carry = sum / 10; 
        p = (p == NULL) ? p : p->next; 
        q = (q == NULL) ? q : q->next; 
    } 
 
    /* 最高位之和如果大于 10，增加一位，新鏈表的節點值為 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 
} 

復雜度分析

時間復雜度：O(max(m, n))，其中 m 和 n 分別為兩個鏈表的長度，需要遞歸調用兩個鏈表的每個節點一次。

空間復雜度：O(1)，未開辟額外存儲空間。