LeetCode 刷题：2. 两数相加

第二题不算太难，思路还是比较好想的，不过写起来稍微有点麻烦，需要注意细节

标题	两数相加
序号	NO.2
难度	中等
标签	递归 链表 数学

1. 题目

---

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

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

你可以假设除了数字 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
• 题目数据保证列表表示的数字不含前导零

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 代码

---

看到这题，思路首先有两个。

1. 从后往前读取这个数，然后将两数相加，再将结果倒过来插到链表中，这个方法更符合人们的直观思想

2. 根据数学两数相加的原理，依次按个位十位百位相加，最后得到结果，这道题正好用到了这个原理，该计算个位相加，插到链表中，再计算十位百位・・・・・・，注意判断两数位数不等以及两数相加后位数多一位的情况。如 99 + 9 = 108

显然，第二种方法比第一种方法好很多，故采用第二种方法。

• 时间复杂度 O (n)

• 空间复杂度 O (n)

• 执行用时：3324ms

• 内存消耗：15.6MB

# 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]:
        lx, ly= l1, l2	     # 保留函数输入l1, l2
        lz = l = ListNode()	 # 待返回链表
        num_tenplace = 0	 # 每次计算结果的十位
        
        while lx or ly:
            # 两数对应位数
            num_x = lx.val if lx else 0
            num_y = ly.val if ly else 0
            # 两位数相加的个位加入单链表
            lz.val = (num_x + num_y + num_tenplace) % 10
            # 两位数相加的十位
            num_tenplace = (num_x + num_y + num_tenplace) // 10
           	
            # 位数+1
            lz.next = ListNode()
            lz_pre = lz
            lz = lz.next
            if (lx):
                lx = lx.next
            if (ly):
                ly = ly.next
        
        # 判断相加最后是否多出一位
        if num_tenplace == 0:
            lz_pre.next = None
        else:
            lz.val = num_tenplace
            lz.next = None
 
        return l

• 执行用时：8ms
• 内存消耗：7.4MB

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int num_tenplace = 0;
    struct ListNode* l = (struct ListNode* )malloc(sizeof(struct ListNode));
    struct ListNode* s_pre, * s = l;
    while(l1 || l2){
        int x = l1 ? l1->val : 0; 
        int y = l2 ? l2->val : 0; 

        s->val = (x + y + num_tenplace) % 10;
        num_tenplace = (x + y + num_tenplace) / 10;

        s->next = (struct ListNode* )malloc(sizeof(struct ListNode));
        s_pre = s;
        s = s->next;
        if(l1)   l1 = l1->next;
        if(l2)   l2 = l2->next;
    }
    if (num_tenplace)
        s->val = num_tenplace, s->next = NULL;
    else
        s_pre->next = NULL;

    return l;

}