Add Two Numbers Leetcode Solution
In this tutorial, we are going to solve a leetcode problem Add Two Numbers in Python.
Task:
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.
Example1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
Solution:
# 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: ListNode, l2: ListNode) -> ListNode:
head1, head2 = l1, l2
if head1 is None:
return head2
if head2 is None:
return head1
A, n = ListNode(0), 0
new_head = A
while (head1 != None) or (head2 != None):
if head1 is None:
m = head2.val + int(n)
n = 0
head2 = head2.next
elif head2 is None:
m = head1.val + int(n)
n = 0
head1 = head1.next
else:
m = head1.val + head2.val + int(n)
n = 0
head1 = head1.next
head2 = head2.next
m = str(m)
if len(m) > 1:
n = m[0]
new_head.next = ListNode(m[1])
else:
new_head.next = ListNode(m)
if ((head1 and head2) == None) and len(m) > 1:
new_head.next.next = ListNode(n)
new_head = new_head.next
return A.next
Steps:
step1: First we add our base case i.e. if either of the head is None then, return the other linked list's head.
step2: Now, we'll create another head of our target linked list A and gave it currently a value of 0, and a variable n = 0 (which is used to store carry).
step3: Then, we apply a while loop which will end if either of the head is None.
step4: if one of the head is None, we'll simply add the other head's value along with the int(n) and then update the n again to 0.
step5: if both of the heads are not None then add both head's value along with the int(n) and add store it to the variable m, don't forget to update the head.
step6: now we'll change the type of m from int to string and checks it's length, if it is more than 1 i.e. we need to add carry which is 0th index of the m and store it in the n and update the new_head. And we also added an edge case i.e. if both of the heads are None and len(m) > 1.
step7: we'll continue this process till loop breaks, then we return the next node of A.
