{"id":3154,"date":"2018-07-14T21:48:51","date_gmt":"2018-07-15T04:48:51","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3154"},"modified":"2021-04-07T23:55:17","modified_gmt":"2021-04-08T06:55:17","slug":"leetcode-445-add-two-numbers-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-445-add-two-numbers-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 445. Add Two Numbers II"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

You are given two\u00a0non-empty<\/b>\u00a0linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.<\/p>\n

You may assume the two numbers do not contain any leading zero, except the number 0 itself.<\/p>\n

Follow up:<\/b>
\nWhat if you cannot modify the input lists? In other words, reversing the lists is not allowed.<\/p>\n

Example:<\/b><\/p>\n

Input:<\/b> (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)\nOutput:<\/b> 7 -> 8 -> 0 -> 7<\/pre>\n
Solution: Simulation<\/strong><\/h1>\n
Using a stack to “reverse” the list. Simulate the addition digit by digit.<\/p>\n
Time complexity: O(l1 + l2)<\/p>\n
Space complexity: O(l1 + l2)<\/p>\n
C++<\/p>\n
\/\/ Author: Huahua\n\/\/ Running time: 40 ms\nclass Solution {\npublic:\n  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {\n    stack<int> s1;\n    stack<int> s2;\n    while (l1) {\n      s1.push(l1->val);\n      l1 = l1->next;\n    }    \n    while (l2) {\n      s2.push(l2->val);\n      l2 = l2->next;\n    }    \n    ListNode* head = nullptr;\n    int sum = 0;\n    while (!s1.empty() || !s2.empty() || sum) {\n      sum += s1.empty() ? 0 : s1.top();\n      sum += s2.empty() ? 0 : s2.top();\n      if (!s1.empty()) s1.pop();\n      if (!s2.empty()) s2.pop();            \n      ListNode* n = new ListNode(sum % 10);\n      sum \/= 10;\n      n->next = head;\n      head = n;      \n    }    \n    return head;      \n  }\n};<\/pre>\n
Related Problems<\/strong><\/h1>\n