2. Add Two Numbers

Approach 1: Iterate through both of the lists simultaneously

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
‚Äč
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 or not l2: return l1 or l2
head = ListNode('a')
a = head
carry = 0
while l1 and l2:
a.next = ListNode((l1.val + l2.val + carry)%10)
carry = (l1.val + l2.val + carry)//10
a = a.next
l1 = l1.next
l2 = l2.next
while l1:
a.next = ListNode((l1.val + carry)%10)
carry = (l1.val + carry)//10
a = a.next
l1 = l1.next
while l2:
a.next = ListNode((l2.val + carry)%10)
carry = (l2.val + carry)//10
a = a.next
l2 = l2.next
if carry != 0:
a.next = ListNode(carry)
return head.next

In this we wil iterate through each of these lists simultaneously and

Time Complexity: O(N), where N = max(len(l1), len(l2))

Space Complexity: O(N), where N = max(len(l1), len(l2))