Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Copy the code

Note:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
Copy the code

parsing

Given two non-empty linked lists representing two non-negative integers. These numbers are stored in the linked list in reverse order, and each of their nodes contains a number. Add the two numbers together and return the sum as a linked list. The sum of the returned results is stored in the linked list in reverse order. And these two numbers don’t contain any leading zeros, except for the number 0 itself.

Actually this question is very simple, is the difficulty as the Medium, it is because the combined process of two Numbers to the list, we need to traverse the two on the list of values, the side of every two values for sum and carry on the operation, if the two basic content already know, the questions were very easy to make.

Initialize a result node and a virtual pointer d node, initialize a carry memory with carry 0, and execute the while loop when L1 is not null or L2 is not null:

  • If the position is empty, it is set to 0; if it is not empty, the node value is used for calculation. Then, the number P at the position can be obtained by adding the two values with carry and modulo operation of 10. Convert it to a ListNode and assign the virtual pointer d.ext; The new carry is obtained by adding both values to carry and dividing by 10
  • Move the D pointer back one bit
  • If L1 is not empty, move back one bit; L2 does the same

After the while ends, carry may still be greater than 0, indicating that carry numbers are still available, so create a new node to store CARRY, assign the node to d. ext, and return result.next.

The time complexity is only related to the longest list, so O(Max (L1, L2)), the space complexity is related to the longest list length, and there may be one more carry, so O(Max (L1, L2)+1).

answer

class Solution(object): def addTwoNumbers(self, l1, l2): result = d = ListNode(-1) carry = 0 while l1 or l2: a = l1.val if l1 else 0 b = l2.val if l2 else 0 p = (a + b + carry) % 10 d.next = ListNode(p) carry = (a + b + carry) //  10 d = d.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None if carry: d.next = ListNode(carry) return result.nextCopy the code

The results

Given the submission in the Python online submission list. Submissions in Python online submissions for Add Two Numbers.Copy the code

The original link

Leetcode.com/problems/ad…

Your support is my biggest motivation