A LeetCode Daily Series — Day 75

In this article, we will explore the problem of solving the “Add Two Numbers” problem using linked lists in Python. This problem is a classic algorithmic challenge often encountered in coding interviews and competitions. We’ll delve into understanding the problem, and then we’ll explore a brute force approach and a more efficient solution.

Add Two Numbers - LeetCode leetcode.com

Can you solve this real interview question? Add Two Numbers

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

The problem statement is as follows: 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. You need to add the two numbers and return the sum as a linked list.

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]

Brute Force Approach

The brute force approach involves converting the linked lists to their respective integer representations, performing the addition, and then converting the result back to a linked list. While this method works, it is not the most efficient due to the overhead of integer conversion.

def addTwoNumbers(
    self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:

    def linked_list_to_num(node):
        num = 0
        count = 1
        while node:
            num += node.val * count
            count = count * 10
            node = node.next
        return num

    def num_to_linked_list(num):
        finalh = ListNode(-1)
        helper = finalh

        while num != 0:
            helper.next = ListNode(num % 10)
            num = num // 10
            helper = helper.next
        return finalh

    num1 = linked_list_to_num(l1)
    num2 = linked_list_to_num(l2)

    result = num1 + num2
    if result == 0:
        return ListNode(0)

    finalh = num_to_linked_list(result)

    return finalh.next

Explanation

1. Conversion Functions: We define two helper functions:

   • linked_list_to_num to convert a linked list to an integer.
   • num_to_linked_list to convert an integer back to a linked list.

2. Sum Calculation: We convert both linked lists (l1 and l2) to their integer representations (num1 and num2), sum them (result), and then convert the result back to a linked list.

3. Edge Case: If the result is zero, we directly return a node with value 0.

Time Complexity: O(N + M), where N and M are the lengths of the two linked lists. This is because we traverse each list once to convert to integers and then traverse the result to convert back to a linked list.

Space Complexity: O(max(N, M)), the space required for the output linked list.

Using Efficient Approach (Iterative Addition)

In this approach, we iterate through both linked lists simultaneously, adding corresponding digits along with any carry from the previous addition. This method avoids converting linked lists to integers and back, making it more efficient in terms of both time and space.

def addTwoNumbers(
    self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
    dummy = ListNode()
    curr = dummy

    carry = 0
    while l1 or l2:
        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0

        val = v1 + v2 + carry

        carry = val // 10
        val = val % 10
        curr.next = ListNode(val)

        curr = curr.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    if carry:
        curr.next = ListNode(carry)

    return dummy.next

Explanation

1. Initialization: We initialize a dummy node (dummy) to help with the linked list creation and a current node pointer (curr) set to this dummy node. We also initialize a carry variable to 0.

2. Iteration: We iterate through both linked lists until we reach the end of both. In each iteration:

   • We get the values of the current nodes of both lists (v1 from l1 and v2 from l2, defaulting to 0 if one list is shorter).
   • We calculate the sum of these values and the carry from the previous iteration (val = v1 + v2 + carry).
   • We update the carry (carry = val // 10) and the current digit value (val = val % 10).
   • We create a new node with val and move the current pointer to this new node.
   • We move to the next nodes in both linked lists l1 and l2.

3. Final Carry Check: After the loop, if there is any remaining carry, we create a new node with this carry value.

4. Return the Result: Finally, we return the next node of the dummy node, which points to the head of the resulting linked list.

Time Complexity: O(max(N, M)), where N and M are the lengths of the two linked lists. We traverse each list once.

Space Complexity: O(max(N, M)), the space required for the output linked list. The space used by the output list is proportional to the length of the longer input list.

Conclusion

In this article, we explored multiple ways to solve the “Add Two Numbers” problem using linked lists. We discussed a brute force approach and one efficient methods. Each method has its advantages and trade-offs in terms of time and space complexity.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

A LeetCode Daily Series — Day 76 | Ritesh Shakya riteshakya.com.np

Today’s problem is called "Remove Nth Node From End of List"