[LeetCode] 2. Add Two Numbers

1. Question

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.

Example 2:

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

Example 3:

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

2. Thoughts

Use Greedy

3. Tips learned

3.1. New Nodes:

how to make new node?

new_node = ListNode(val=5)

4. My solution

class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        len_l1, len_l2 = 1, 1

        temp_node = l1
        while temp_node.next != None:
            temp_node = temp_node.next
            len_l1 += 1

        temp_node = l2
        while temp_node.next != None:
            temp_node = temp_node.next
            len_l2 += 1

        iter_num = 0
        if len_l1 >= len_l2:
            long_node = l1
            short_node = l2
            iter_num = len_l2
        else:
            long_node = l2
            short_node = l1
            iter_num = len_l1

        overFlow = False
        for i in range(iter_num):
            long_node.val += short_node.val
            if overFlow:
                long_node.val += 1
                overFlow = False

            if long_node.val >= 10:
                long_node.val -= 10
                overFlow = True

            if i == iter_num - 1:
                break

            long_node = long_node.next
            short_node = short_node.next

        while overFlow:
            if long_node.next == None:
                new_node = ListNode(val=1, next=None)
                long_node.next = new_node
                overFlow = False
            else:
                long_node = long_node.next
                long_node.val += 1
                overFlow = False
                if long_node.val >= 10:
                    long_node.val -= 10
                    overFlow = True

        if len_l1 >= len_l2:
            return l1
        else:
            return l2

1568/1568 cases passed (58 ms)
Your runtime beats 75.23 % of python3 submissions
Your memory usage beats 24.5 % of python3 submissions (17.3 MB)

5. AI Solution and Improvements

The provided solution for adding two numbers represented by linked lists works, but it's more complex than necessary. The main issue is the handling of different lengths of linked lists and the manual tracking of overflows. We can simplify this by using a single loop and a carry variable. Here’s an improved approach:

1. Single Loop: Iterate through both lists simultaneously, adding corresponding digits along with any carry from the previous step.

2. Carry: Keep track of the carry (if the sum of two digits is 10 or more).

3. Handling Different Lengths: If one list is longer than the other, continue the process with the longer list.

4. Final Carry: If there's a carry after the end of the loop, add a new node with this carry value.

Here's the revised code:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # Initialize the dummy head of the result list and a carry variable
        dummy_head = ListNode(0)
        current = dummy_head
        carry = 0

        # Iterate through lists l1 and l2
        while l1 or l2:
            # Sum the values of the two nodes and the carry
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            sum = carry + x + y

            # Update carry for next calculation
            carry = sum // 10

            # Create a new node with the digit value and attach it to the result list
            current.next = ListNode(sum % 10)
            current = current.next

            # Move to the next nodes in l1 and l2
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        # Check if there is any remaining carry
        if carry > 0:
            current.next = ListNode(carry)

        # The dummy head's next node is the actual head of the result list
        return dummy_head.next

This code is more concise and avoids unnecessary complexity, making it easier to understand and maintain. It handles different list lengths and carries more effectively, offering a clean solution to the problem.