Leetcode 2: Add Two Numbers

Problem Description

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.

Thought Process

First I thought about picking the longer list and iterating through it, adding the digits from the shorter list as I go. However in this scenario you are only given pointer to the head of the linked list, so I would have to iterate through the shorter list to get its length. Instead I decided to iterate through both lists at the same time in a while loop checking if either of the lists is not None. This way I can add the digits from both lists and handle the carry if the sum is greater than or equal to 10. This way I can also handle the case where one list is longer than the other without having to check the lengths beforehand, I handle other list being longer by checking if it is None in the loop condition and if so not moving forward in that list and making its value to 0.

Another thing to consider was how will I return the result, more so how will I initialise the result linked list. I decided to use a dummy node to simplify the code, this way I can just return the next node of the dummy node at the end. This way I don’t have to check if the result linked list is empty or not within the loop, slowing the code down.

Other than these 2 issues I didn’t have any major problems with this problem apart from the carry still existing after the loop ends, which I initially handled by checking if the carry is greater than 0 and adding a new node with the carry value to the result linked list.

Code

# 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]:
        carry=0
        head=ListNode(0)
        curr=head
        while l1 or l2:
            val1=l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            val=val1+val2+carry
            if val>=10:
                carry=1
                val=val%10
            else:
                carry=0
            new_node=ListNode(val)
            curr.next=new_node
            curr=new_node
            if l1:
                l1=l1.next
            if l2:
                l2=l2.next
        if carry:
            curr.next=ListNode(carry)
        return head.next

However I quickly thought about adding the carry check simply into my while loop condition, this makes the code a bit cleaner and shorter, so I decided to do that instead. The code is now simpler and easier to read.

# 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]:
        carry=0
        head=ListNode(0)
        curr=head
        while l1 or l2 or carry:
            val1=l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            val=val1+val2+carry
            if val>=10:
                carry=1
                val=val%10
            else:
                carry=0
            new_node=ListNode(val)
            curr.next=new_node
            curr=new_node
            if l1:
                l1=l1.next
            if l2:
                l2=l2.next
        return head.next

Complexity Analysis

Time Complexity

The time complexity of this solution is O(max(m, n)) where m and n are the lengths of the two linked lists. This is because we are iterating through both lists at the same time, and we will iterate through each list and 1 extra time at most because of the carry, but that is generally negligible compared to the lengths of the lists.

Space Complexity

The space complexity is O(max(m, n)) as well, since we are creating a new linked list to store the result. In the worst case, the result linked list will have the same length as the longer of the two input linked lists plus one extra node for the carry, which is still O(max(m, n)).

Difficulty

This problem is considered medium on Leetcode. It requires a good understanding of linked lists and how to manipulate them, as well as handling edge cases like carry and different lengths of the lists. I found it to be a good exercise in working with linked lists and thinking about how to handle different scenarios efficiently.

Final Thoughts

I really like this problem because It is a good example of how to use a dummy node to simplify code and edge cases. It also forces you to change your typical way of thinking about how to handle lists. At least I’m personally too used to just having the size of the list easily and peformantly accessible, so this problem was a good exercise in thinking about how to handle lists without that luxury. I think creativity stems from limitations, and this problem is a good example of that.