题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解析

新建一个链表来存储结果，主要问题是处理进位和两个数长度不同

  • 进位
    • 用一个变量保存进位，每次计算完进行更新
  • 长度不同
    • 用x, y分别表示两个要加的数，如果其中一个已经到头了就为0
    • 避免了单独处理进位1在较长的那个数且多出来的部分都是9的情况

      代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  12.         ListNode* dummy = new ListNode(-1);
  13.         ListNode* h = dummy;
  14.         int sign = 0;
  15.         while (l1 || l2) {
  16.             int x = l1 ? l1->val : 0;
  17.             int y = l2 ? l2->val : 0;
  18.             int sum = x + y + sign;
  19.             h->next = new ListNode(sum % 10);
  20.             h = h->next;
  21.             sign = sum / 10;
  22.             l1 = l1 ? l1->next : l1;
  23.             l2 = l2 ? l2->next : l2;
  24.         }
  25.         if (sign) h->next = new ListNode(1);
  26.         return dummy->next;
  27.     }
  28. };