LeetCode2：两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

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

顺序遍历：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         ListNode *sum =new ListNode;
13         ListNode *head=sum;
14         int givein=0;
15         while(l1!=NULL && l2!=NULL){
16             sum->next=new ListNode;
17             sum=sum->next;
18             sum->val=l1->val+l2->val+givein;
19             if(sum->val>=10){
20                 sum->val-=10;
21                 givein=1;
22             }
23             else givein=0;
24             //sum->next=new ListNode;
25             //sum=sum->next;
26             l1=l1->next;
27             l2=l2->next;
28         }
29         ListNode *unfinished = l1==NULL?l2:l1;
30         while(unfinished!=NULL){
31             sum->next=new ListNode;
32             sum=sum->next;
33             sum->val=unfinished->val+givein;
34             if(sum->val>=10){
35                 sum->val-=10;
36                 givein=1;
37             }
38             else givein=0;
39             //sum->next=new ListNode;
40             //sum=sum->next;
41             unfinished=unfinished->next;
42         }
43         if(givein!=0){
44             sum->next=new ListNode;
45             sum->next->val =1;
46         }
47 
48     ListNode *temp=head;
49     head=head->next;
50     delete temp;
51     return head;
52     }
53 };

这里有两种方法，一种是先获得两个链表的长度，然后为长度短的补0，使两个链表一样长在做加法。还可以像上面代码一样处理。

这里需要注意的是，最后返回head->next，需要将head释放掉，不然多次调用会导致溢出。

附上一个较为简洁的写法，更具效率。

 1 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 2     ListNode dummyHead = new ListNode(0);
 3     ListNode p = l1, q = l2, curr = dummyHead;
 4     int carry = 0;
 5     while (p != null || q != null) {
 6         int x = (p != null) ? p.val : 0;
 7         int y = (q != null) ? q.val : 0;
 8         int sum = carry + x + y;
 9         carry = sum / 10;
10         curr.next = new ListNode(sum % 10);
11         curr = curr.next;
12         if (p != null) p = p.next;
13         if (q != null) q = q.next;
14     }
15     if (carry > 0) {
16         curr.next = new ListNode(carry);
17     }
18     return dummyHead.next;
19 }
20 
21 作者：LeetCode
22 链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
23 来源：力扣（LeetCode）
24 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。