algoadvance

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]
Explanation: 342 + 465 = 807.

Clarifying Questions:

  1. Will the input always be two non-empty linked lists? Yes, the problem description specifies that the linked lists are non-empty.

  2. Are the digits stored in reverse order? Yes, the digits are stored in reverse order.

  3. What should we return if both linked lists represent the number zero? If both are zero, the sum should be zero in the format of a linked list, e.g., [0].

Code:

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

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Calculate the sum
        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)

        # Move to the next elements in the list
        current = current.next
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

Strategy:

  1. Initialize Variables:
    • Use a dummy node to simplify the result list creation.
    • A current node pointer to build the new linked list.
    • A carry variable to keep track of the carry-over value during addition.
  2. Iterate Through ListNodes:
    • Loop through l1 and l2 while either has nodes left or there is a carry to handle.
    • Extract values from the current nodes of l1 and l2, defaulting to zero if the node is None.
  3. Sum and Handle Carry:
    • Calculate the sum of the values and carry.
    • Create a new node with the digit part of the sum and attach it to the current node.
    • Update the carry to be the tens part of the sum (total // 10).
  4. Move to Next Nodes:
    • Move the current pointer to the new node.
    • Move to the next nodes in l1 and l2 if they are available.

Time Complexity:

The time complexity of this solution is O(max(m, n)), where m and n are the lengths of l1 and l2. This is because we iterate through both linked lists simultaneously, and the length of the resulting list will depend on the longer of the two input lists.

Space Complexity:

The space complexity is O(max(m, n)) due to the new linked list that we create to store the result, which is proportional to the length of the longer input list plus one additional space if there is a carry at the end.

Try our interview co-pilot at AlgoAdvance.com