地址 https://leetcode-cn.com/problems/sum-lists-lcci/
给定两个用链表表示的整数,每个节点包含一个数位。 这些数位是反向存放的,也就是个位排在链表首部。 编写函数对这两个整数求和,并用链表形式返回结果。 示例: 输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295 输出:2 -> 1 -> 9,即912 进阶:思考一下,假设这些数位是正向存放的,又该如何解决呢? 示例: 输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295 输出:9 -> 1 -> 2,即912
解答
模拟加法 从低位向高位计算。恰好链表也是逆序存放的,从个位进行相加,要创建一个额外的进位变量
/** * 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 add=0; ListNode* ans= new ListNode(0); ListNode* p = ans; while(l1!=NULL && l2!=NULL){ int sum = add+l1->val+l2->val; add = sum/10; sum = sum%10; p->next = new ListNode(sum); p=p->next; l1=l1->next;l2=l2->next; } if(l1==NULL){ while(l2!=NULL){ int sum = add+l2->val; add = sum/10; sum = sum%10; p->next = new ListNode(sum); p=p->next; l2=l2->next; } } if(l2==NULL){ while(l1!=NULL){ int sum = add+l1->val; add = sum/10; sum = sum%10; p->next = new ListNode(sum); p=p->next; l1=l1->next; } } if(add!=0){ p->next = new ListNode(add); } return ans->next; } };