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     int getLength(ListNode *head)
12     {
13         int num=0;
14         while(head)
15         {
16             ++num;
17             head=head->next;
18         }
19         return num;
20     }
21     void Carry(ListNode *head)
22     {
23         bool isCarry=false;
24         ListNode *tmp;
25         while(head)
26         {
27             if(isCarry)++(head->val);
28             if(head->val>=10)
29             {
30                 head->val=(head->val)%10;
31                 isCarry=true;
32             }else isCarry=false;
33             tmp=head;
34             head=head->next;
35         }
36         if(isCarry)tmp->next=new ListNode(1);
37     }
38     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
39         if(l1==NULL || l2==NULL)return NULL;
40         int length1=getLength(l1);//获取链表长度
41         int length2=getLength(l2);
42         if(length2<length1)//使l2始终指向最长的链表，方便将两个链表相加
43         {
44             ListNode *tmp=l1;
45             l1=l2;
46             l2=tmp;
47         }
48         ListNode *head=l2;
49         while(l1)//将两个链表相加
50         {
51             l2->val=l2->val+l1->val;
52             l1=l1->next;
53             l2=l2->next;
54         }
55         Carry(head);//进位
56         return head;
57     }
58 };

　　好吧，其实可以不用改变原链表的

 1 class Solution {
 2 public:
 3     void Carry(ListNode *head)
 4     {
 5         bool isCarry=false;
 6         ListNode *tmp;
 7         while(head)
 8         {
 9             if(isCarry)head->val=head->val+1;
10             if(head->val>=10)
11             {
12                 isCarry=true;
13                 head->val=head->val%10;
14             }else isCarry=false;
15             tmp=head;
16             head=head->next;
17         }
18         if(isCarry)tmp->next=new ListNode(1);
19     }
20     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
21         if(l1==NULL && l2==NULL)return NULL;
22         ListNode *head=new ListNode(0);
23         ListNode *tmp=head;
24         while(true)
25         {
26             if(l1)
27             {
28                 tmp->val=tmp->val+l1->val;
29                 l1=l1->next;
30             }
31             if(l2)
32             {
33                 tmp->val=tmp->val+l2->val;
34                 l2=l2->next;
35             }
36             if(l1 || l2)
37             {
38                 tmp->next=new ListNode(0);
39                 tmp=tmp->next;
40             }else break;
41         }
42         Carry(head);//进位
43         return head;
44     }
45 };

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。