add two numbers
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.
1Input: l1 = [2,4,3], l2 = [5,6,4]
2Output: [7,0,8]
3Explanation: 342 + 465 = 807.
4Example 2:
Solution
The nave solution is to convert the linked lists to integers, add them, and convert the result back to a linked list. This approach however is three times slower than doing it in one pass.
Since the number is reversed, we can do elementary school addition, by adding both numbers, and passing the 1 (if there is one) to the next set of numbers to be added.
Please note the lists do not need to be of the same length. As such, it's important for the algorithm to properly handle reaching the end of one list early.
1class Node:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6def addTwoNumbers(l1, l2):
7 dummy_head = node = Node(-1)
8 v = 0
9 while l1 or l2 or v:
10 v, r = divmod((l1.val if l1 else 0) + (l2.val if l2 else 0) + v, 10)
11 node.next = Node(r)
12 node = node.next
13 l1 = (l1.next if l1 else None)
14 l2 = (l2.next if l2 else None)
15 return dummy_head.next
This may be the first time you come across the use of a dummy_head; those are very useful, as they prevent us from treating the start of our list as a special case. It also means we return dummy_head.next.
Note: divmod is being used for clarity and succinctness, however // and % are slightly more performant as they don't require preserving the current frame while a function call to divmod is executed.
Time and Space Complexity