当前位置：首页 > news >正文

力扣HOT100之链表：2. 两数相加

news 来源：原创 2025/8/22 14:34:28

这道题就是按照正常的数学思维去做的，设置一个标志位flag用来标记进位的情况，当发生进位时设置为1，否则设置为0，初始时设置为0。我们同时遍历两个链表，将两个节点的值相加，再加上上一位的进位flag，再对结果求余，就得到了应该在本节点存储的值，当有一条链表提前结束遍历时，直接用进位flag加上未遍历结束的节点的值，当两条链表都遍历结束时，还需要判断flag是否为0，若不为0（必然为1），还需要新建一个节点，将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) {int flag = 0;ListNode* result = new ListNode();ListNode* virtual_head = result;while(l1 || l2){if(l1 && l2){int value = (l1 -> val + l2 -> val + flag) % 10;result -> next = new ListNode(value);flag = l1 -> val + l2 -> val + flag >= 10 ? 1 : 0;result = result -> next;l1 = l1 -> next;l2 = l2 -> next;}else if(!l1 && l2){  //l1已经遍历完了，但是l2还没结束int value = (l2 -> val + flag) % 10;result -> next = new ListNode(value);flag = l2 -> val + flag >= 10 ? 1 : 0;result = result -> next;l2 = l2 -> next;}else if(!l2 && l1){  //l2已经遍历完了，但是l1还没结束int value = (l1 -> val + flag) % 10;result -> next = new ListNode(value);flag = l1 -> val + flag >= 10 ? 1 : 0;result = result -> next;l1 = l1 -> next;}}if(flag != 0)  //处理进位的情况result -> next = new ListNode(flag);return virtual_head -> next;}
};

AC之后看了下灵神的代码，同样提供了两种思路，一种是迭代法（和我的方法一样），另一种是递归法。灵神的迭代法写的比较简洁漂亮，比我的代码简短多了，贴出来学习一下。

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode dummy; // 哨兵节点ListNode* cur = &dummy;int carry = 0; // 进位while (l1 || l2 || carry) { // 有一个不是空节点，或者还有进位，就继续迭代if (l1) {carry += l1->val; // 节点值和进位加在一起l1 = l1->next; // 下一个节点}if (l2) {carry += l2->val; // 节点值和进位加在一起l2 = l2->next; // 下一个节点}  cur = cur->next = new ListNode(carry % 10); // 每个节点保存一个数位carry /= 10; // 新的进位}return dummy.next; // 哨兵节点的下一个节点就是头节点}
};

看了下递归法的代码，虽然很简单，但是我感觉比迭代法难懂一些，就记住迭代法这种解法就行了。

相关文章：