02.05、链表求和

02.05、[中等] 链表求和 1、题目描述

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

2、解题思路

本题要求对两个链表表示的整数进行相加。链表中的每个节点代表一个数位，且个位数在链表的头部。即，链表是以反向存放的方式表示整数的。我们需要编写一个函数来求这两个整数的和，并将结果以链表的形式返回。

初始化链表和指针： 使用一个虚拟头节点 head 来简化链表操作。cur 用于遍历和构建新链表。cur1 和 cur2 分别用于遍历链表 l1 和 l2。add 用于记录当前位的加和及进位。 遍历链表： 遍历 l1 和 l2，对对应位的数字进行加和。处理进位情况（即当前位的和超过 10 时的进位）。 创建新节点： 将当前位的和取个位数，作为新节点的值。更新进位值（即当前位和除以 10 的结果）。 处理剩余进位： 如果处理完所有节点后还有进位，需在结果链表中添加一个新节点。 返回结果： 返回虚拟头节点 head 的下一个节点，即实际结果链表的头节点。 3、代码实现与详细注释 class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode head; // 虚拟头节点，简化链表操作 ListNode *cur = &head; // 当前节点，用于构建结果链表 ListNode *cur1 = l1; // 遍历链表 l1 ListNode *cur2 = l2; // 遍历链表 l2 int add = 0; // 存储当前位的和及进位 // 遍历链表，直到 l1、l2 都为空且没有进位 while (cur1 || cur2 || add) { if (cur1) { add += cur1->val; // 加上 l1 当前节点的值 cur1 = cur1->next; // 移动到 l1 的下一个节点 } if (cur2) { add += cur2->val; // 加上 l2 当前节点的值 cur2 = cur2->next; // 移动到 l2 的下一个节点 } // 创建新节点，存储当前位的和的个位数 ListNode* newnode = new ListNode(add % 10); cur->next = newnode; // 将新节点链接到结果链表 cur = cur->next; // 移动到结果链表的下一个节点 add /= 10; // 更新进位值 } return head.next; // 返回结果链表的头节点（跳过虚拟头节点） } }; 4、关键点总结 链表的遍历： 使用 cur1 和 cur2 遍历两个输入链表。每次从两个链表中取值并加和，处理进位情况。 进位处理： 在加和过程中，处理进位并更新 add 的值。如果存在剩余进位，继续在结果链表中添加节点。 结果链表的构建： 使用虚拟头节点来简化链表的处理。最终返回虚拟头节点的下一个节点，即实际结果链表的头节点。 5、时间复杂度与空间复杂度 时间复杂度： O(max(m, n))，其中 m 和 n 分别是链表 l1 和 l2 的长度。我们只遍历了两个链表一次。空间复杂度： O(max(m, n))，因为链表的长度决定了结果链表的长度。