每日一题（两数相加）

每日一题（两数相加）

2. 两数相加 - 力扣（LeetCode）

思路

思路：

1. 由于链表从头开始向后存储的是低权值位的数据，所以只需要两个指针p1和p2，分别从链表的头节点开始遍历。同时创建一个新的指针newhead，（用于构造新链表，将创建的新节点进行头插）。并在这个构造的新链表的相应的节点中存储p1和p2对应值的相加结果。

2. 但是p1和p2所对应的节点的值相加可能会产生进位，所以创建一个pre变量用于存储相应的进位值。（假设p1和p2所指向的节点的值是n1和n2，那么产生的进位值就是：pre = （n1+n2+pre）/10;同时对应新的创建的节点的值就应该是 (pre+n1+n2)%10;。对应代码如下：

       struct ListNode* p1=NULL,   *p2 = NULL, *newhead = NULL,*tail = NULL;
       int pre = 0;//pre一开始的值必须是0
       if(!l1)
       return l2;
       if(!l2)
       return l1;
       p1 = l1;
       p2 = l2;
       while(p1&&p2)
       {
   struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
               newnode->val = (p1->val+p2->val+pre)%10;
               newnode->next = NULL;
           if(newhead == NULL)
           {
               //更新pre（进位）
               pre = (p1->val + p2->val)/10;
               newhead = tail = newnode;
           }
           else
           {
                //更新pre（进位）
               pre = (p1->val + p2->val+pre)/10;
               tail->next = newnode;
               tail = tail->next;
           }
           p1 = p1->next;
           p2 = p2->next;
       }
   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

3. 假如遇到的链表有以下这种长短不一的情况：就需要接着遍历那个较长的链表，将较长的链表中未被遍历的节点的值与pre的值一起参与运算，（因为这俩个链表的相同长度的部分的链表的最后一个节点中存储的值也会存在相加产生进位的情况）。代码实现如下：

   while(p2)//当p2没有走完
           {
   struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
           newnode->val = (p2->val+pre)%10;
           newnode->next = NULL;
   		//更新pre
           pre = (p2->val+pre)/10;
           p2 = p2->next;
           tail->next = newnode;
           tail = tail->next;
           } 
           while(p1)//当p1没有走完
           {
   struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
           newnode->val = (p1->val+pre)%10;
           newnode->next = NULL;
           //更新pre
           pre = (p1->val+pre)/10;
           p1 = p1->next;
           tail->next = newnode;
           tail = tail->next;
           }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

   

4. 假如链表是如下这几种情况，即便是将两个链表都遍历之后，此时的进位值仍然是1，说明此时的相加计算还没有结束，此时还需要一个节点来存储进位值，所以在将两个链表遍历结束之后，需要对pre的值进行判断，假若pre的值是0，则直接返回newhead即可，pre的值若是1，则还需要创建一个节点。代码如下：

   if(pre)
           {
   struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
           newnode->val = pre;
           newnode->next = NULL;
           tail->next = newnode;
           tail = tail->next;
       }
   1
   2
   3
   4
   5
   6
   7
   8

   

代码实现

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* p1=NULL,   *p2 = NULL, *newhead = NULL,*tail = NULL;
    int pre = 0;
    if(!l1)
    return l2;
    if(!l2)
    return l1;
    p1 = l1;
    p2 = l2;
    while(p1&&p2)
    {
struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
            newnode->val = (p1->val+p2->val+pre)%10;
            newnode->next = NULL;
        if(newhead == NULL)
        {
            //更新pre（进位）
            pre = (p1->val + p2->val)/10;
            newhead = tail = newnode;
        }
        else
        {
             //更新pre（进位）
            pre = (p1->val + p2->val+pre)/10;
            tail->next = newnode;
            tail = tail->next;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
         
       if(pre)
        {
struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newnode->val = pre;
        newnode->next = NULL;
        tail->next = newnode;
        tail = tail->next;
    }
    return newhead;
}
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

完结

两数相加的链表习题的分析就到这里啦，若有不足，欢迎评论区指正，下期见！