Add Two Numbers

Leetcode link: https://leetcode.com/problems/add-two-numbers/submissions/

Question

Given 2 non-empty singly linked list which represent numbers stored in reverse order, with each node representing a single digit, add the 2 numbers together and return a new linked list representing the result.

The 2 linked lists may not be of the same length.

Example:

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807.

Implementation

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

head = None

curr = None

carry = 0

# add the two linked lists until one of them is empty

while l1 and l2:

sum = l1.val + l2.val + carry

carry = sum // 10

sum = sum % 10

# initialise new linked list for result

if curr is None:

head = ListNode(sum, None)

curr = head

else:

new_node = ListNode(sum, None)

curr.next = new_node

curr = curr.next

l1 = l1.next

l2 = l2.next

# add remaining of l1 if any

while l1:

sum = l1.val + carry

carry = sum // 10

sum = sum % 10

new_node = ListNode(sum)

curr.next = new_node

curr = curr.next

l1 = l1.next

# add remaining of l2 if any

while l2:

sum = l2.val + carry

carry = sum // 10

sum = sum % 10

new_node = ListNode(sum)

curr.next = new_node

curr = curr.next

l2 = l2.next

# if carry is remaining, we create a new node for it

if(carry):

new_node = ListNode(carry, None)

curr.next = new_node

return head

• Time complexity: O(n + m) where n is the length of first linked list and m is the length of the second linked list.
• Space complexity: O(n + m) for creation of new linked list