{"id":3293,"date":"2018-07-25T23:43:48","date_gmt":"2018-07-26T06:43:48","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3293"},"modified":"2018-09-11T21:11:39","modified_gmt":"2018-09-12T04:11:39","slug":"leetcode-2-add-two-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-2-add-two-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2. Add Two Numbers"},"content":{"rendered":"

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

You are given two\u00a0non-empty<\/b>\u00a0linked lists representing two non-negative integers. The digits are stored in\u00a0reverse order<\/b>\u00a0and 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

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

Input:<\/b> (2 -> 4 -> 3) + (5 -> 6 -> 4)\r\nOutput:<\/b> 7 -> 0 -> 8\r\nExplanation:<\/b> 342 + 465 = 807.<\/pre>\n
Solution: Simulation<\/strong><\/h1>\n
Simulate the addition, draw two numbers (one each) from l1, l2, if list is empty draw 0.<\/p>\n
Using a dummy head makes things easier.<\/p>\n
Time complexity: O(max(l1,l2))<\/p>\n
Space complexity: O(max(l1,l2))<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\n\/\/ Running time: 28 ms\r\nclass Solution {\r\npublic:\r\n  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {\r\n    ListNode dummy(0);\r\n    ListNode* tail = &dummy;\r\n    int sum = 0;\r\n    while (l1 || l2 || sum) {\r\n      sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);\r\n      l1 = l1 ? l1->next : nullptr;\r\n      l2 = l2 ? l2->next : nullptr;\r\n      tail->next = new ListNode(sum % 10);\r\n      sum \/= 10;\r\n      tail = tail->next;\r\n    }            \r\n    return dummy.next;\r\n  }\r\n};<\/pre>\n\n<\/div>
Java<\/h2>\n
\n\n
\/\/ Author: Huahua\r\n\/\/ Running time: 30 ms\r\nclass Solution {\r\n  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {\r\n    int sum = 0;\r\n    ListNode dummy = new ListNode(0);\r\n    ListNode tail = dummy;\r\n    while (l1 != null || l2 != null || sum != 0) {\r\n      if (l1 != null) {\r\n        sum += l1.val;\r\n        l1 = l1.next;\r\n      }\r\n      if (l2 != null) {\r\n        sum += l2.val;\r\n        l2 = l2.next;\r\n      }\r\n      tail.next = new ListNode(sum % 10);\r\n      sum \/= 10;\r\n      tail = tail.next;\r\n    }\r\n    return dummy.next;\r\n  }\r\n}<\/pre>\n\n<\/div>
Python3<\/h2>\n
\n\n
\"\"\"\r\nAuthor: Huahua\r\nRunning time: 112 ms\r\n\"\"\"\r\nclass Solution:\r\n  def addTwoNumbers(self, l1, l2):\r\n    s = 0\r\n    dummy = ListNode(0)\r\n    tail = dummy\r\n    while l1 or l2 or s > 0:      \r\n      s += (l1.val if l1 else 0) + (l2.val if l2 else 0)\r\n      l1 = l1.next if l1 else None\r\n      l2 = l2.next if l2 else None\r\n      tail.next = ListNode(s % 10)\r\n      s \/\/= 10\r\n      tail = tail.next\r\n    return dummy.next<\/pre>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n