目录
题目描述:
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
解法:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry = 0; ListNode* h1 = l1; ListNode* h2 = l2; if(l1 == NULL){ return l2; }else if(l2 == NULL){ return l1; } ListNode* head = NULL; ListNode* cur = NULL; int val = 0; while(h1 != NULL && h2 != NULL){ val = carry + h1->val + h2->val; if(val >= 10){ carry = 1; val -= 10; }else{ carry = 0; } if(head == NULL){ head = new ListNode(val); cur = head; }else{ cur->next = new ListNode(val); cur = cur->next; // should point to the next node } h1 = h1->next; h2 = h2->next; } while(h1 != NULL){ val = carry + h1->val; if(val >= 10){ carry = 1; val -= 10; }else{ carry = 0; } cur->next = new ListNode(val); h1 = h1->next; cur = cur->next; } while(h2 != NULL){ val = carry + h2->val; if(val >= 10){ carry = 1; val -= 10; }else{ carry = 0; } cur->next = new ListNode(val); h2 = h2->next; cur = cur->next; } if(carry != 0){ // if carry != 0, should add an additional node cur->next = new ListNode(carry); } return head; }};