链表两数相加时的进位异常问题排查

核心问题拆解 #

你的代码存在三个关键错误，导致部分测试用例结果异常：

1. 提前返回跳过进位处理：当两个链表长度相同时，相加完成后直接return l1，完全跳过了后续的进位修正逻辑。比如测试用例[8,8,6]+[2,2,2]相加后得到[10,10,8]，但没有处理进位，最终返回错误结果。
2. 长链表拼接逻辑失效：当其中一个链表更长时，没有将剩余节点正确接入结果链表。比如l2更长时，仅将node1指向node2，但未把node2的节点连接到l1的末尾，导致这部分节点的值未被纳入最终计算。
3. 进位处理不彻底：仅遍历一次链表处理进位，无法应对连续进位场景（比如[9,9,9]+[1]，第一次处理后会产生新的需进位节点，当前逻辑无法二次处理）。

推荐修复方案（使用哑节点构建结果） #

更规范的做法是用哑节点构建结果链表，在相加过程中实时处理进位，逻辑更清晰且避免上述问题：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0); // 哑节点，简化链表头节点处理
        ListNode* curr = &dummy;
        int carry = 0; // 存储进位值

        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            // 计算当前位总和：包含进位+两个链表当前节点值（如果存在）
            int sum = carry;
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
            // 更新进位和当前节点值
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
        }

        return dummy.next;
    }
};

代码说明

• 哑节点：避免处理链表头为空的特殊情况，直接从哑节点的next开始构建结果链表。
• 实时进位处理：每一位相加时直接计算进位，无需后续遍历修正，彻底解决连续进位问题。
• 全覆盖循环条件：循环包含carry != 0，确保最后一位相加产生的进位也能被处理（比如[9,9]+[1]会生成[0,0,1]）。

基于原有代码的针对性修复 #

如果想保留原有代码结构，需调整以下三点：

1. 移除提前返回逻辑：删除相加后的if(!node1 && !node2){return l1;}，确保无论链表长度是否相同，都执行进位处理。
2. 修复长链表拼接：将剩余节点正确接入l1末尾：

   // 替换原有拼接逻辑
   ListNode* tail = l1;
   while (tail->next != nullptr) tail = tail->next; // 找到l1的尾节点
   if (node2 != nullptr) {
       tail->next = node2; // 将l2剩余节点接到l1末尾
   }
   

3. 循环处理进位：重复遍历直到没有进位产生：

   node1 = l1;
   bool hasCarry;
   do {
       hasCarry = false;
       ListNode* curr = node1;
       while (curr != nullptr && curr->next != nullptr) {
           if (curr->val > 9) {
               curr->next->val += curr->val / 10;
               curr->val %= 10;
               hasCarry = true;
           }
           curr = curr->next;
       }
       // 处理最后一个节点的进位
       if (curr != nullptr && curr->val > 9) {
           curr->next = new ListNode(curr->val / 10);
           curr->val %= 10;
           hasCarry = true;
       }
   } while (hasCarry);
   

内容的提问来源于stack exchange，提问作者Marut Kashyap