考虑到有进位的问题,首先想到的思路是:
先分位求总和得到 totalsum,然后再将totalsum按位拆分转成链表;
1 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
2 int sum = 0;
3 int i = 1;
4 while(l1 != NULL && l2 != NULL)
5 {
6 sum += i*(l1->val + l2->val);
7 i *= 10;
8 l1 = l1->next;
9 l2 = l2->next;
10 }
11 while(l1 != NULL)
12 {
13 sum += i * (l1->val);
14 i *= 10;
15 l1 = l1->next;
16 }
17 while(l2 != NULL)
18 {
19 sum += i * (l2->val);
20 i *= 10;
21 l2 = l2->next;
22 }
23 //fen
24 ListNode *head = new ListNode(0);
25 ListNode *p = head;
26 if(sum == 0) return head;
27 while(sum!=0)
28 {
29 p->next = new ListNode(sum%10);
30 p = p->next;
31 sum /= 10;
32 }
33 return head->next;
34 }
修修改改总算是通过了基本测试,但并不是100%通过;
这就奇怪了,为什么运算得好好的,遇到这组测试就偏偏出了问题。输出中间结果一看,才知道是 int 型溢出了。因此将变量 sum 和变量 i 都从int型换成 long long 型。这下总该行了吧?
没想到呀,还有更长的测试数据。
静下心来想一想,既然输入的数据是链表的形式,必然会有超过 long long 长度的情况。此解决方案存在巨大的隐患!!!
换一种思维方式,只需要关注同等位的相加,进位1或者不进位。问题很简单嘛,同等位相加加入到新链表中,若有进位则记录到下次同等位的相加中....
1 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
2 ListNode *head = new ListNode(0);
3 ListNode *p = head;
4 int sum = 0;
5 while(l1 != NULL || l2 != NULL)
6 {
7 if(l1 != NULL)
8 {
9 sum += (l1->val);
10 l1 = l1->next;
11 }
12 if(l2 != NULL)
13 {
14 sum += (l2->val);
15 l2 = l2->next;
16 }
17 p->next = new ListNode(sum%10);
18 p = p->next;
19 sum /= 10;
20 }
21 if(sum != 0)
22 p->next = new ListNode(sum);
23 return head->next;
24 }
回顾下链表的创建个输出,以头结点不存内容为例。
1、链表的创建:
1 ListNode* CreatList()
2 {
3 ListNode *head = new ListNode(0);
4 ListNode *p = head;
5 int x = 1;
6 while(1)
7 {
8 cin>>x;
9 if(x == -1)
10 break;
11 p->next = new ListNode(x);
12 p = p->next;
13 }
14 return head;
15 }
2、打印链表:
1 void PrintList(ListNode *head)
2 {
3 ListNode* p = head;
4 while(p->next!=NULL)
5 {
6 p = p->next;
7 cout<<p->val<<"->";
8 }
9 cout<<endl;
10 }