题目内容

给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。

示例：

• 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
  输出：2 -> 1 -> 9，即912

进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

• 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
  输出：9 -> 1 -> 2，即912

解题思路与代码

这种题它没有给你说链表的节点范围，就不要贸然的想要去用遍历节点然后存储在一个int里。因为很可能存不下。就算是换size_t类型也不行。

方法一：对位相加法

由于由于输入的两个链表都是反向存放数字的位数的，因此两个链表中同一位置的数字可以直接相加。首先我们可能会察觉到一个问题，就是相加超过10会产生进位问题，所以我们就先设置一个进位变量nextBit将它置为0.之后我们逐位去遍历链表，将当前的 进位值 与 两个链表当前位的和相加起来。具体而言，如果当前两个链表处相应位置的数字为v1,v2 则这个的和sum = v1 + v2 + nextBit。我们创建一个新链表，每次将（sum%10)作为一个节点的值存进链表。然后再新的进位值设置为(sum /10)。

还有一个问题便是我们链表会出现长短不一的情况那怎么办呢？很好办，将短的链表的值设为0即可。这个设计很巧妙，具体可以看代码：

代码

/*** 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) {ListNode *head = nullptr, *pos = nullptr;int nextBit = 0; while(l1 || l2){int v1 = l1 ? l1->val : 0;int v2 = l2 ? l2->val : 0;int sum = v1 + v2 +nextBit;if(!head){head = pos = new ListNode(sum % 10);}else{pos->next = new ListNode(sum % 10);pos = pos->next;}nextBit = sum / 10;if(l1) l1 = l1->next;if(l2) l2 = l2->next;}if(nextBit) pos->next = new ListNode(nextBit);return head;}
};

给出这个代码的复杂度分析：
时间复杂度：O(max(m,n)),其中m，n分别是链表l1，l2的节点个数，我们需要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
空间复杂度：O(1),没有用到额外的数据结构。

进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

先开个玩笑，其实可以先翻转链表，然后再进行同为相加操作，hh。这种写法我就不写了，没什么必要。

那换一种思路想想，有没有什么数据结构，可以让我们实现先加链表的最后面的节点呢？
答案是：栈（stack） 。我们可以分别把链表l1，l2的节点分别压入栈中。此时取出来的元素必定是相同位数。如果有的栈先取完了，和刚刚一样，当做0就行。

注意，虽然说，这里的进阶是让你去思考，如果你拿我的代码去leetcode上去提交，题解肯定是不通过的，这是因为，leetcode里面的案例都是个位数是排在前面的，而我们这个进阶思考是让你将最高位排在最前面。

而将最高位排在最前面其实就运用到了一个技巧，就是用循环来插入头节点。也就是反转链表

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {stack s1, s2;while (l1) {s1.push(l1 -> val);l1 = l1 -> next;}while (l2) {s2.push(l2 -> val);l2 = l2 -> next;}int carry = 0;ListNode* head = nullptr;while (!s1.empty() or !s2.empty() or carry != 0) {int a = s1.empty() ? 0 : s1.top();int b = s2.empty() ? 0 : s2.top();if (!s1.empty()) s1.pop();if (!s2.empty()) s2.pop();int cur = a + b + carry;carry = cur / 10;cur %= 10;auto pos = new ListNode(cur);pos -> next = head;head = pos;}return head;}
};

给出这个代码的复杂度分析：
时间复杂度：O(max(m,n)),其中m，n分别是链表l1，l2的节点个数，我们需要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
空间复杂度：空间复杂度主要取决于我们把链表内容放入栈中所用的空间。

总结

这道题说难不算很难，但也不算简单。处处考验了大家对于操作链表的细节。大家可能都知道要同位相加，但同位相加的操作却怎么也写不对，这就是经验啦，做的题越多，对于细节的处理就越到位，代码也就越容易通过。