[力扣 Hot100]Day28 两数相加

题目描述

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

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

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

出处

思路

逆序两数相加也是逆序返回，可以用一个进位位来模拟(进位位只有可能是0或1)。要考虑谁长谁短的问题，最终结果可能需要在最长的基础上再新加一位(新建一个尾结点)。

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p=l1;
        ListNode* q=l2;
        ListNode* res=l1;
        int num=0,sum=0;
        while(p->next&&q->next){
            sum=p->val+q->val+num;
            if(sum<10){
                p->val=sum;
                num=0;
            }
            else{
                p->val=sum-10;
                num=1;//进位
            }
            p=p->next;
            q=q->next;
        }
        sum=p->val+q->val+num;
        if(sum<10){
            p->val=sum;
            num=0;
        }
        else{
            p->val=sum-10;
            num=1;//进位
        }
        if(!p->next&&!q->next){//一样长
            if(num){
                p->next=new ListNode(1);
                return res;
            }
        }
        if(q->next&&!p->next){//l2比l1长
            p->next=q->next;
        }
        p=p->next;
        while(p){//l1比l2长
            sum=p->val+num;
            if(sum<10){
                p->val=sum;
                num=0;
            }
            else{
                p->val=sum-10;
                num=1;//进位
            }
            q=p;
            p=p->next;
        }
        if(num){
            q->next=new ListNode(1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58