题目链接

LeetCode

题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例 1：

445. 两数相加 II - 图1

输入： l1 = [7,2,4,3], l2 = [5,6,4]
输出： [7,8,0,7]

示例 2：

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [8,0,7]

示例 3：

输入： l1 = [0], l2 = [0]
输出： [0]

提示：

  • 链表的长度范围为 [1, 100]
  • 0 <= node.val <= 9
  • 输入数据保证链表代表的数字无前导 0

进阶： 如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

解题思路

方法一：反转链表

先将两个链表反转，然后结果用头插法

  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.         l1 = reverseHead(l1);
  15.         l2 = reverseHead(l2);
  16.         ListNode* hair = new ListNode();
  17.         int carry = 0;
  18.         while(l1||l2||carry){
  19.             int x = 0;
  20.             int y = 0;
  21.             if(l1){
  22.                 x = l1->val;
  23.                 l1 = l1->next;
  24.             }
  25.             if(l2){
  26.                 y = l2->val;
  27.                 l2 = l2->next;
  28.             }
  29.             int tmp = x+y+carry;
  30.             carry = tmp/10;
  31.             // 头插法
  32.             ListNode* cur = new ListNode(tmp%10);
  33.             cur->next = hair->next;
  34.             hair->next = cur;
  35.         }
  36.         return hair->next;
  37.     }
  38.     // 反转链表
  39.     ListNode* reverseHead(ListNode* head){
  40.         if(head==nullptr||head->next==nullptr){
  41.             return head;
  42.         }
  43.         ListNode* res = reverseHead(head->next);
  44.         head->next->next = head;
  45.         head->next = nullptr;
  46.         return res;
  47.     }
  48. };


  • 时间复杂度 O(n)

  • 空间复杂度 O(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.       stack<int> s1,s2;
    15.       while(l1){
    16.           s1.push(l1->val);
    17.           l1 = l1->next;
    18.       }
    19.       while(l2){
    20.           s2.push(l2->val);
    21.           l2 = l2->next;
    22.       }
    23.       ListNode* hair = new ListNode();
    24.       int carry = 0;
    25.       while(!s1.empty()||!s2.empty()||carry){
    26.           int x = 0;
    27.           int y = 0;
    28.           if(!s1.empty()){
    29.               x = s1.top();
    30.               s1.pop();
    31.           }
    32.           if(!s2.empty()){
    33.               y = s2.top();
    34.               s2.pop();
    35.           }
    36.           int tmp = x+y+carry;
    37.           carry = tmp/10;
    38.           // 头插法
    39.           ListNode* cur = new ListNode(tmp%10);
    40.           cur->next = hair->next;
    41.           hair->next = cur;
    42.       }
    43.       return hair->next;
    44.   }
    45. };


  • 时间复杂度 O(max(m,n))

  • 空间复杂度 O(m+n)