Leetcode-2.两数相加
Leetcode-2.两数相加
1.错误解法
idea: 先遍历两个链表，计算出两个数的数值（十进制），后将两数相加，再将 和 的各位转换为链表的各个节点值。
个人觉得想法是完全没错的，但是要知道计算机一次所能存储的数字位数有限，有的样例就过不去（尽管我使用了long long类型）。比如：
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 long long value1 = 0, value2 = 0; 13 long long count1 = 0, count2 = 0; 14 //计算两个数 15 while(l1) 16 { 17 value1 += l1->val*pow(10, count1); 18 l1 = l1->next; 19 count1++; 20 } 21 while(l2) 22 { 23 value2 += l2->val*pow(10, count2); 24 l2 = l2->next; 25 count2++; 26 } 27 //求和->转换->加入单链表 28 long sum = value1+value2; 29 ListNode* ans, *p, *temp; 30 ans = new ListNode(sum%10); 31 p = ans; 32 sum /= 10; 33 while(sum) 34 { 35 //尾插法 36 temp = new ListNode(sum%10); 37 p->next = temp; 38 p = temp; 39 sum /= 10; 40 } 41 return ans; 42 } 43 };
2.正解
idea：（参考了官方题解）遍历两个链表（p， q），节点不为空取值，为空则取0，需要另外加入一个进位量（carry）来表示进位，将两个链表值与进位值相加，和取余建立新节点（更新carry=sum/10），最后处理一下最后可能的进位（再新建一个节点）。
1 class Solution { 2 public: 3 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 4 ListNode *Head, *p, *q, *current;//待返回链表头节点 5 Head = new ListNode(0); 6 p = l1; q = l2; current = Head; 7 int carry = 0;//进位 8 while(p != NULL || q != NULL) 9 { 10 int x = (p != NULL)?p->val:0; 11 int y = (q != NULL)?q->val:0;//不为空则取值，为空取0 12 int sum = carry + x + y; 13 carry = sum/10; 14 current->next = new ListNode(sum%10);//余数即为节点值 15 current = current->next; 16 if(p != NULL) 17 { 18 p = p->next; 19 } 20 if(q != NULL) 21 { 22 q = q->next; 23 } 24 } 25 if(carry > 0)//处理最后的进位 26 { 27 current->next = new ListNode(carry); 28 } 29 return Head->next; 30 } 31 };
投递海康威视等公司10个岗位 >