两数相加

问题描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

问题来源：leetcode编程题：两数相加

思考分析

思路：遍历每一种可能出现的"元素对"，按照加法原则进行相加，由于加法需要设置一个进位标志。当进行加法运算时，考虑是否有来自地位的进位 和 是否产生进位。

分析可能会出现的情况：

• 如果两个整数位数相同，同时结束两个链表的遍历。
• 如果有其中一个整数的位数较长，其中一个链表先结束遍历，其余的部分为0。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* pHead =  new ListNode(0);       //新链表的头节点指针

        ListNode* pNode = pHead;  //pNode节点指针对新链表进行操作
        
        bool flag = 0;   //进位标志，true表示进位
        int sum = 1;        //保存相加的结果
        //1.遍历每一个节点元素
        while ( (l1 != NULL) || (l2 != NULL) )
        {//两个链表没有完全遍历结束
            if (l1 == NULL)
            {//l1代表的链表遍历结束

                if (flag) sum = l2->val + 1;  //判断是否有进位
                else sum = l2->val;

                flag = sum/10;               //判断是否产生进位
                
                pNode->next = new ListNode(sum%10); //创建节点并写入结果
                pNode = pNode->next;
                //l1 = NULL;             //没有变化        
                l2 = l2->next;                     
  
            }
            else if (l2 == NULL)
            {//l2代表的链表遍历结束

                //l1->val为相加的结果
                if (flag) sum = l1->val + 1;  //判断是否有进位
                else sum = l1->val;

                flag = sum/10;               //判断是否产生进位

                pNode->next = new ListNode(sum%10);
                pNode = pNode->next;
                //l2 = NULL;             //没有变化        
                l1 = l1->next;  
            }
            else
            {//l1、l2节点都没有结束
                //(l1->val + l2->val)为相加的结果
                if (flag) sum = (l1->val + l2->val) + 1;  //判断是否有进位
                else sum = (l1->val + l2->val);

                flag = sum/10;               //判断是否产生进位

                pNode->next = new ListNode(sum%10);
                pNode = pNode->next;
                l2 = l2->next;     
                l1 = l1->next; 
            }

        }

        //2.最后判断有无进位
        if (flag)
        {
            //最高位值为1
            pNode->next = new ListNode(1);
            pNode = pNode->next;
        }
        pNode->next = NULL;

        //返回结果
        return (pHead->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
  
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
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
 

总结

在coding中，一开始的思路是先创建节点空间 --> 写入当前节点值 --> 偏移下一个节点 --> ... --> 最后返回首节点指针。但是实现过程中，发现当我将pNode指针偏移到下一个节点，再创建新节点的时候，，之前的创建的节点编程了孤立节点，不能构成链表。纠结了好半天。。。
看到其他coder的写法，改变了一下顺序，先创建node空间并将当前节点的next指针指向这个node空间，问题就解决了！！！ 不过这样首节点就没有意义了，最后返回pHead->next节点。

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/103114636