Difficulty: Medium
You are given two non-empty linked lists representing two non-negative integers. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
language c：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode* ans = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode* p = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode t; p->next = NULL; ans = p; bool carry = false; //对应位两数都有数字时，相加 int count = 0; while(l1 != NULL && l2 != NULL) { //非一次相加 另建节点 if (count != 0) { struct ListNode* lino = (struct ListNode *)malloc(sizeof(struct ListNode)); lino->next = p->next; p->next = lino; p = p->next; } int b = 0; //上一次有进位 if(carry) { b++; } int a1 = l1->val; int a2 = l2->val; b += (a1+a2); if (b >= 10) { carry = true;//告诉下一次计算有进位 p->val = (b-10); } else { carry = false;//无进位 p->val = b; } //p = p->next; l1 = l1->next; l2 = l2->next; count++; } //两数位数不同时则有一个数会有剩余位 while (l1 != NULL) { struct ListNode* lino = (struct ListNode *)malloc(sizeof(struct ListNode)); lino->next = p->next; p->next = lino; p = p->next; int sum = 0; if (carry) { sum++; } sum += l1->val; if (sum >9) { carry = true; sum -= 10; } else carry = false; p->val = sum; //p = p->next; l1 = l1->next; } while(l2 != NULL) { struct ListNode* lino = (struct ListNode *)malloc(sizeof(struct ListNode)); lino->next = p->next; p->next = lino; p = p->next; int sum = 0; if (carry) { sum++; } sum += l2->val; if (sum >9) { carry = true; sum -= 10; } else carry = false; p->val = sum; //p = p->next; l2 = l2->next; } if (carry) { struct ListNode* lino = (struct ListNode *)malloc(sizeof(struct ListNode)); lino->next = p->next; p->next = lino; p = p->next; p->val = 1; } return ans; }PS：链表的新建上容易犯错！以及进位标志的保留。
struct ListNode* p = (struct ListNode *)malloc(sizeof(struct ListNode)); p->next = NULL; struct ListNode* lino = (struct ListNode *)malloc(sizeof(struct ListNode)); lino->next = p->next; p->next = lino; p = p->next;