問題描述

給定兩個非空鏈表，表示兩個非負整數。鏈表中的每個節點存儲一個數字，數字的存儲順序為逆序（即個位在鏈表頭部）。要求將這兩個數字相加，并以相同形式返回一個表示和的鏈表。

示例：

1. 輸入：l1 = [2,4,3]，l2 = [5,6,4]
   輸出：[7,0,8]
   解釋：342 + 465 = 807

2. 輸入：l1 = [0]，l2 = [0]
   輸出：[0]

3. 輸入：l1 = [9,9,9,9,9,9,9]，l2 = [9,9,9,9]
   輸出：[8,9,9,9,0,0,0,1]

提示：

• 每個鏈表中的節點數在范圍 [1, 100] 內。
• 0 <= Node.val <= 9
• 題目數據保證鏈表表示的數字不含前導零。

問題分析

1. 鏈表結構：鏈表是一種線性數據結構，每個節點包含一個值和指向下一個節點的指針。本題中，鏈表的節點值表示數字的每一位。
2. 逆序存儲：鏈表的頭節點存儲的是數字的個位，鏈表的尾節點存儲的是數字的最高位。
3. 進位處理：在逐位相加時，可能需要處理進位的情況。

解題思路

1. 創建虛擬頭節點：為了方便操作，創建一個虛擬頭節點 dummy，其 next 指針指向結果鏈表的頭節點。
2. 遍歷鏈表：同時遍歷兩個鏈表，逐位相加，并處理進位。
3. 處理剩余部分：如果其中一個鏈表先遍歷完，繼續處理另一個鏈表的剩余部分。
4. 處理最終進位：如果最后還有進位，需要在結果鏈表末尾添加一個新節點。

代碼實現

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {// 創建虛擬頭節點struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* current = dummy;int carry = 0;  // 進位標志// 遍歷兩個鏈表while (l1 || l2) {// 獲取當前節點的值（如果鏈表為空，則為0）int n1 = l1 ? l1->val : 0;int n2 = l2 ? l2->val : 0;// 計算當前位的和int sum = n1 + n2 + carry;carry = sum / 10;  // 更新進位sum = sum % 10;    // 當前位的值// 創建新節點存儲當前位的值current->next = (struct ListNode*)malloc(sizeof(struct ListNode));current->next->val = sum;current->next->next = NULL;current = current->next;// 移動鏈表指針if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}}// 如果最后還有進位，添加一個新節點if (carry > 0) {current->next = (struct ListNode*)malloc(sizeof(struct ListNode));current->next->val = carry;current->next->next = NULL;}// 返回結果鏈表的頭節點return dummy->next;
}

代碼解析

1. 虛擬頭節點：dummy 是一個虛擬頭節點，用于簡化鏈表操作。最終返回的結果鏈表是 dummy->next。
2. 逐位相加：通過 n1 和 n2 獲取當前節點的值，加上進位 carry，計算當前位的和 sum。
3. 進位處理：carry = sum / 10 用于更新進位，sum = sum % 10 用于獲取當前位的值。
4. 鏈表遍歷：通過 l1 和 l2 的指針移動，逐位處理兩個鏈表。
5. 最終進位：如果最后還有進位，需要在結果鏈表末尾添加一個新節點。

注意事項

1. 鏈表為空的處理：在計算 n1 和 n2 時，需要判斷鏈表是否為空，避免訪問空指針。
2. 內存管理：每次創建新節點時，需要使用 malloc 分配內存，并確保在程序結束時釋放內存（如果需要）。

示例運行

以示例 1 為例：

• 輸入：l1 = [2,4,3]，l2 = [5,6,4]
• 計算過程：
  • 第一位：2 + 5 = 7，無進位，結果鏈表為 [7]
  • 第二位：4 + 6 = 10，進位為 1，當前位為 0，結果鏈表為 [7,0]
  • 第三位：3 + 4 + 1 = 8，無進位，結果鏈表為 [7,0,8]
• 輸出：[7,0,8]

總結

本題考察了鏈表的操作和進位處理。通過創建虛擬頭節點和逐位相加的方式，可以高效地解決該問題。時間復雜度為 O(max(n, m))，其中 n 和 m 分別為兩個鏈表的長度。
最開始我還以為是正常的相加呢，那不得麻煩死，還得反轉列表。結果不需要，直接加就好，一下子容易太多了。另外學會了如何新建一個結點， struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));我就一直想為什么(ListNode*)malloc(sizeof(struct ListNode));為什么不對，原來是設置的就有問題。在代碼中，dummy 和 current 的類型聲明為 struct ListNode*，但在 malloc 和類型轉換時，使用了 (ListNode*)，這可能會導致編譯錯誤。正確的類型轉換應該是 (struct ListNode*)。

在C語言中，malloc 返回的是 void* 類型。雖然在某些編譯器中，顯式類型轉換是允許的，但嚴格來說，這種轉換是不必要的。如果你的編譯器支持，可以去掉類型轉換。