LeetCode50天刷题计划（Day 1—— 两数相加 11.00-12.30）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

机试太菜了每次都被秒杀
所以趁暑假好好练习一下吧~

一、题目描述

题目

两数相加
给你两个 非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

二、思路

①两个链表分别从头遍历，逐位相加
（1）需要保存本次进位
（2）需要保存本次结果
②遍历条件：
（1）两个链表只要有一个非空就需要往后进行
（2）另一个为空的数值可以设置为0
③遍历结束：
如果最终一位的进位不为0，需要把进位项添加在链表后面

三、代码

1.python

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        #和的表头和指针（表头最后要删去）
        r=p=ListNode()
        #进位
        add=0
        #如果两个表有一个有元素，另一个空值设置为0
        while(l1 or l2):
            x=l1.val if l1 else 0
            y=l2.val if l2 else 0
            temp=x+y+add #带上进位
            add=0
            if temp>=10:
                add=1
                temp=temp-10
            #写入新值，指针前移
            p.next=ListNode(temp)
            p=p.next
            if l1 : l1=l1.next
            if l2 : l2=l2.next
        #如果最后仍有进位
        if(add):
            p.next=ListNode(add)
        return r.next #删去表头结点

2.c++

/** * 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) {
    
        //设置结果链表头r和指针p和进位记录add
        ListNode *r= new ListNode();
        ListNode *p=r;
        int add=0;
        
        while(l1 || l2){
    
            //本轮的加数和
            int x = l1?l1->val:0;
            int y = l2?l2->val:0;
            int temp=x+y+add;
            add=0;
            //进位
            if(temp>=10){
    
                add=1;
                temp=temp-10;
            }
            //记录结果链表
            p->next=new ListNode(temp);
            //指针向前移动
            p=p->next;
            if(l1) l1=l1->next;
            if(l2) l2=l2->next;
        }
        //添加进位项
        if(add) p->next=new ListNode(add);
        return r->next;
    }
};