【LeetCode第二题】两数相加-CSDN博客

本文链接：https://blog.csdn.net/Go_forward_/article/details/132246513

题目：两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 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
题目数据保证列表表示的数字不含前导零

思路：遍历两个链表并注意进位

同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。

代码：击败了43.94%

/**
 * 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 * sum = new ListNode();
        ListNode* ret = sum;
        int value = (l1->val + l2->val) % 10;
        int carry = (l1->val + l2->val) / 10; 
        sum->val = value;
        l1 = l1->next;
        l2 = l2->next;
        while (l1 != nullptr && l2 != nullptr) {
            value = (l1->val + l2->val + carry) % 10;
            carry = (l1->val + l2->val + carry) / 10;
            sum->next = new ListNode(value);
            sum = sum->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1 == nullptr && l2 != nullptr) {
            value = (l2->val + carry) % 10;
            carry = (l2->val + carry) / 10;
            sum->next = new ListNode(value);
            sum = sum->next;
            l2 = l2->next;
        }
        while (l2 == nullptr && l1 != nullptr) {
            value = (l1->val + carry) % 10;
            carry = (l1->val + carry) / 10;
            sum->next = new ListNode(value);
            sum = sum->next;
            l1 = l1->next;
        }
        if (carry != 0) {
            sum->next = new ListNode(carry);
        }
        return ret;
    }
};

在这里插入图片描述

优化：击败了91.58%

修改了变量名：列表的名字head更恰当，使用名字tail来当列表的哨兵。进位名保留使用carry，比较恰当。
调整结构使得更清晰：由三个while循环（两个列表都非空情况、l1为空l2不为空情况、l2为空l1不为空情况），修改为一个while循环（l1或l2不为空），

/**
 * 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 *head = nullptr;
        // 通过哨兵tail指向后继节点来扩充链表
        ListNode *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry != 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};