LeetCode 2 两数相加（链表）

数据结构是这样的：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { } };

如果暴力考虑，将List1的表全遍历一次得到sum1,再将List2的表全遍历一次得到sum2

将sum2按数字拆分成数字数组（后/10），需要注意int范围，可以开到long long进行。

 

在此使用第二种思路，引入一个进位标志carry

每次均按位相加即可，注意讨论一表为空的情况。

AC代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(-1); //-1初始化 ListNode *p = l1, *q = l2, *tmp = head; int carry = 0; while(p || q) { int sum = 0; int x = (p != NULL) ? p->val : 0; int y = (q != NULL) ? q->val : 0; sum = x + y + carry; tmp->next = new ListNode(sum % 10); tmp = tmp->next; carry = sum / 10; if(p)p = p->next; //一定是p还有的时候 if(q)q = q->next; //同上 } if(carry) tmp->next = new ListNode(carry); return head->next; } };