動畫圖解“兩數相加”，小學生都能看懂
本文轉載自微信公眾號「程序員小熊」，作者Dine。轉載本文請聯系程序員小熊公眾號。
前言
大家好，我是來自于華為的程序員小熊。今天給大家帶來一道各互聯網大廠面試中?？嫉纳婕暗芥湵硐嚓P的中檔題題，即力扣上的第 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)，未開辟額外存儲空間。
