这道题是LeetCode里的第2道题。
题目要求:
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
这道题的条件判断很简单,如下:
1.是否为尾节点
2.是否产生进位
3.是否等于9
4.是否需要拓展空间
代码如下:
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 *p = l1, *q = l2; 13 int add, carry = 0;//carry标志进位 14 15 while (1) { 16 add = p->val + q->val + carry; 17 p->val = add % 10; 18 if (add > 9)carry = 1; 19 else carry = 0; 20 if (p->next == NULL || q->next == NULL)break; 21 p = p->next; 22 q = q->next; 23 } 24 //这里就相当于是一个链表只有一个节点,另一个链表加上这个一个节点的数值 25 if (p->next) {//list1 26 p = p->next; 27 q = p; 28 while (carry) {//是否需要进位 29 if (q->val == 9) {//是否等于9 30 if (q->next == NULL) {//是否是最后一个节点 31 q->val = 0; 32 q->next = (ListNode*)malloc(sizeof(ListNode)); 33 q->next->val = 1; 34 q->next->next = NULL; 35 break; 36 } 37 q->val = 0; 38 q = q->next;} 39 else {q->val++;carry = 0;} 40 } 41 return l1; 42 } 43 44 if (q->next) {//list2 45 q = q->next; 46 l2 = q; 47 while (carry) { 48 if (q->val == 9) { 49 if (q->next == NULL) { 50 q->val = 0; 51 q->next = (ListNode*)malloc(sizeof(ListNode)); 52 q->next->val = 1; 53 q->next->next = NULL; 54 break; 55 } 56 q->val = 0; 57 q = q->next;} 58 else {q->val++;carry = 0;} 59 } 60 p->next = l2; 61 return l1; 62 } 63 64 if (carry) { 65 q = (ListNode*)malloc(sizeof(ListNode)); 66 q->next = NULL; 67 q->val = 1; 68 p->next = q; 69 } 70 return l1; 71 } 72 };
运行结果:
个人总结:在设计算法初期,造成了许多代码的累赘,以上代码是经过优化后得到的。但是在这里两个if条件中还是会有代码的重复,但能够做出来我就已经很开心了。(^-^)V
内容来源于网络如有侵权请私信删除
- 还没有人评论,欢迎说说您的想法!