LeetCode: Add digits of 2 Linked Lists into a New Linked List

Problem statement: Add 2 Numbers

Intuition

Given 2 linked lists of digits of 2 numbers, we create a normal list of digits that's the summation of digits from the 2 linked lists.

The sum of 2 digits ranges from 0 to 18. For sums greater than 9 such as 13, we keep a separate variable named remainder that contains the value 1 that is added to the digit sum of the next iteration.

With the list of summed digits at hand, we construct an empty linked list and push the digits there. For each digit, we create a list node, traverse to the end of the linked list, and add the node.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # while l1 is not None:
        #     print(l1.val)
        #     l1  = l1.next
        sum_digits = []
        remainder = 0
        while l1 is not None or l2 is not None:
            dig_sum = remainder #add the reminder from the previous iteration
            
            if l1 is not None:
                #print('l1: ', l1.val)
                l1_digit = l1.val
                dig_sum += l1_digit
                l1 = l1.next
            if l2 is not None:
                #print('l2: ', l2.val)
                l2_digit = l2.val
                dig_sum += l2_digit
                l2 = l2.next
            if dig_sum > 9:
                remainder = 1 #2 digit sums are between 10 - 18
                dig_sum = dig_sum %10 #keep the fist digit to be inserted in final linked list
            else:
                remainder = 0
            sum_digits.append(dig_sum)

        if remainder == 1: #if there is remainder after all digit summations
            sum_digits.append(1)

        #insert into linked list
        head_node =None #to be returned
        for digit in sum_digits:
            tmp_node = ListNode(digit, None)
            if head_node is None:

                head_node = tmp_node #first node in the linkedlist
            else:
                last_node = head_node
                while last_node.next: #traverse the linked list to get to the end of list
                    last_node = last_node.next
                last_node.next = tmp_node #add the new node to the end of list
        return head_node
                
        

Time Complexity of Insert Operations

1. Loop Iteration: The for loop iterates over each digit in the sum_digits list. Let's denote the length of the sum_digits list as m.
2. Insertion Operation: For each iteration of the loop, the insert code of the linked list is executed. The time complexity of inserting a value into the linked list depends on the current size of the linked list.
3. Insertion Time Complexity: In the worst-case scenario, the linked list has n nodes. Inserting an element at the end of a linked list involves traversing the list until the last node, which takes O(n) time. Therefore, the time complexity of inserting a single value into the linked list is O(n).
4. Total Time Complexity: Since there are m values in the sum_digits list and each insertion operation takes O(n) time, the total time complexity of the entire loop is O(m * n).