add-two-numbers（LeetCode）

原题来自牛客网LeetCode：链接

给定两个代表非负数的链表，数字在链表中是反向存储的（链表头结点处的数字是个位数，第二个结点上的数字是十位数…），求这个两个数的和，结果也用链表表示。

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出： 7 -> 0 -> 8

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

示例1

输入 {0},{0}

输出 {0}

示例2

输入 {0},{1}

输出 {1}

思路

数字已经是反向存储了，因此逐位相加然后进位即可，用一个变量out记录是否有进位。

用尾插法添加每一个结点即可，开头第一个结点可以设为0方便尾插，最后返回head->next即可。

代码如下：

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(!l1&&!l2) return NULL; ListNode *ans,*p=NULL; int out=0,num,sum=0; p=new ListNode(0); ans=p; while(l1||l2||out){ sum=0; if(l1){ sum+=l1->val; l1=l1->next; } if(l2){ sum+=l2->val; l2=l2->next; } if(out) sum+=1; out=(sum>=10? 1:0); num=sum%10; ListNode *tmp=new ListNode(num); p->next=tmp; p=tmp; } return ans->next; } };