leetcode：2. 两数相加

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
[中等] 2. 两数相加 - 图1

  1. 输入：l1 = [0], l2 = [0]
  2. 输出：[0]

示例 2：

  1. 输入：l1 = [0], l2 = [0]
  2. 输出：[0]

示例 3：

  1. 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  2. 输出：[8,9,9,9,0,0,0,1]

解答 & 代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  14.         ListNode* dummyHead = new ListNode();    // 结果链表的虚拟头节点
  15.         ListNode* pre = dummyHead;                // 结果链表的前一个节点
  17.         ListNode* cur1 = l1;        // 指向 l1 链表的节点
  18.         ListNode* cur2 = l2;        // 指向 l2 链表的节点
  19.         int carry = 0;                // 进位
  20.         // 同时遍历两个链表
  21.         while(l1 != nullptr || l2 != nullptr || carry != 0)
  22.         {
  23.             // 求和
  24.             int sum = (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val) + carry;
  25.             ListNode* cur = new ListNode(sum % 10);
  26.             carry = sum / 10;    // 更新进位
  27.             pre->next = cur;
  28.             pre = cur;
  29.             l1 = l1 == nullptr ? nullptr : l1->next;
  30.             l2 = l2 == nullptr ? nullptr : l2->next;
  31.         }
  32.         return dummyHead->next;
  33.     }
  34. };

复杂度分析：设两个链表较长的一个长度为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(1)：结果链表本身复杂度不计

执行结果：

  1. 执行结果：通过
  3. 执行用时：24 ms, 在所有 C++ 提交中击败了 77.35% 的用户
  4. 内存消耗：69.4 MB, 在所有 C++ 提交中击败了 74.74% 的用户