2. Add Two Numbers

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8]

Input: l1 = [0], l2 = [0] Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: ` [8,9,9,9,0,0,0,1]`

Constraints:

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.

Solution Approach

The solution iteratively adds corresponding digits from the two linked lists, including any carry from the previous addition, to produce a new linked list representing the sum.

Algorithm

1. Digit-by-Digit Addition: The solution iteratively adds digits from the two linked lists, simulating the manual addition process, starting from the least significant digit.
2. Carry Management: It efficiently handles the carry from each addition, ensuring that if the sum of two digits exceeds 9, the carry is added to the next pair of digits.
3. Linked List Construction: The result is stored in a new linked list, with each node representing a digit of the sum, making the solution well-suited for cases where the input numbers have different lengths.

   Complexity

   time complexity: O(max(M, N)) M and N are the lengths of the two linked lists space complexity: O(max(M, N))

Implement

    # Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            val = carry
            if l1:
                l1, val = l1.next, val + l1.val
            if l2:
                l2, val = l2.next, val + l2.val 
            carry, val = divmod(val,10)
            cur.next = ListNode(val)
            cur = cur.next

        return dummy.next
        

    
    

Twitter  facebook  Email