力扣2题 解题思路和步骤 C++代码实现,力扣(leetcode)

链表相加问题的基本理解

力扣第2题要求将两个非空链表表示的非负整数相加，并以相同形式返回结果。这道题考察的核心是对链表数据结构的操作能力，特别是处理不同长度链表时的遍历技巧。每个链表节点存储一个数字（0-9），且数字以逆序方式存储，这使得从个位开始相加的操作变得直接。

为什么选择链表作为数据结构？链表可以灵活处理任意长度的数字，不受固定位数限制。解题时需要特别注意进位处理，当某位相加结果超过9时，需要将进位值加到下一位的计算中。这种场景在常规的整数运算中很常见，但用链表实现时需要开发者手动管理进位传递过程。

算法设计的关键步骤分解

解决该问题的算法可以分为三个主要步骤：同步遍历两个链表、逐位计算和与进位、处理结果链表的构建。需要创建哑节点(dummy node)作为结果链表的起始点，这个技巧可以简化链表头节点的处理。使用while循环同时遍历两个输入链表，直到所有节点都被处理完毕。

在遍历过程中，如何高效处理不同长度链表？可以采用"或"条件判断，只要任一链表还有未处理节点就继续循环。对于已经到达终端的链表，可以将其当前数字视为0。每次迭代需要计算三个值的和：链表1当前节点值、链表2当前节点值和来自上一位的进位值。计算后，新节点的值应为和对10取模，而新的进位值为和除以10取整。

边界条件与特殊情况处理

实际编码时需要特别注意几种边界情况：当两个链表长度不同时，较长链表的剩余部分仍需与进位相加；所有节点处理完毕后，若仍有未处理的进位（如999+1=1000的情况），需要额外创建一个节点存储的进位。

让我们看一个典型测试案例：输入l1 = [9,9,9,9,9,9,9]，l2 = [9,9,9,9]，输出应为[8,9,9,9,0,0,0,1]。这个案例验证了算法能否正确处理：不同长度链表、连续进位、最终额外进位等情况。通过这类边界测试可以确保代码的鲁棒性。

时间复杂度与空间复杂度分析

该算法的时间复杂度为O(max(m,n))，其中m和n分别是两个链表的长度。因为需要完整遍历较长的链表一次。空间复杂度同样为O(max(m,n))，主要是存储结果链表所需的空间，最坏情况下（如产生进位）结果链表会比输入链表多一个节点。

有没有可能优化空间效率？实际上，可以修改原链表节点而不新建链表，但这样会破坏输入数据，不符合函数式编程的无副作用原则。在工程实践中，根据具体场景选择是否允许修改输入数据结构。本解法采用创建新链表的保守方式，确保函数调用不会产生意外副作用。

完整C++代码实现与逐行解析

class Solution {
public:
    ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy(0); // 创建哑节点简化头节点处理
        ListNode curr = &dummy;
        int carry = 0;
        
        while (l1 || l2 || carry) {
            int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
        return dummy.next;
    }
};