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