Problem Description
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.
Example 1:
Input: l1 = [7,2,4,3], l2 = [5,6,4] Output: [7,8,0,7]
Example 2:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [8,0,7]
Example 3:
Input: l1 = [0], l2 = [0] Output: [0]
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.
Follow up: Could you solve it without reversing the input lists?
The description was taken from https://leetcode.com/problems/add-two-numbers-ii.
Problem Solution
#O(Max(M,N)) Time, O(1) Space
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
num_one, num_two = 0, 0
while l1 or l2:
if l1:
num_one *= 10
num_one += l1.val
l1 = l1.next
if l2:
num_two *= 10
num_two += l2.val
l2 = l2.next
num_three = num_one + num_two
dummy = ListNode(0)
output = dummy
if num_three == 0:
return dummy
while num_three:
output.next = ListNode(num_three%10)
num_three //= 10
output = output.next
previous, current = None, dummy.next
while current:
bridge = current.next
current.next = previous
previous = current
current = bridge
return previousProblem Explanation
In the first variation of this problem, the two numbers were in reverse order so it was easy for us to iterate through and sum the least significant node from each number.
In this variation, the two numbers are not in reverse order. We could obviously reverse both lists and make this problem the exact same as the first one, but let's think about how we could solve this without reversing the input lists.
We could instead reverse the output list.
We will iterate through both lists and sum both numbers. Then, using that sum, we will create an output linked list where we will initialize each new node as the least significant digit of the sum. Once we have created the linked list, the ordering will be least significant to most significant moving from left to right. We will want that ordering backward so we will reverse the linked list and return it.
Let's start by initializing two number variables that we will use to convert the values of both lists.
num_one, num_two = 0, 0
Then, while we have nodes in either list, we will multiply each corresponding number by ten so we have a placeholder for the next most significant bit since we're moving from left to right over a number in the correct order. We will then place the number of the current node and iterate to the next node until we reach the end of both lists.
while l1 or l2:
if l1:
num_one *= 10
num_one += l1.val
l1 = l1.next
if l2:
num_two *= 10
num_two += l2.val
l2 = l2.next
Once we have both numbers, we will get the sum.
num_three = num_one + num_two
Now that we have the sum, we can begin building our output list.
Let's create a dummy node and set our output pointer to it. This allows us to avoid handling the logic for setting a head node.
dummy = ListNode(0)
output = dummy
Before moving any further let's first check that we have a list we need to build so we don't run into any errors when trying to reverse this thing. If the sum of the two numbers is zero, we can just return the dummy node that we instantiated with the value of zero.
if num_three == 0:
return dummy
If we have a sum, we will now build the list for it.
Until the third number is zero, we will instantiate a node with the value of the least significant digit, then chop the least significant digit off and iterate to the next node.
while num_three:
output.next = ListNode(num_three%10)
num_three //= 10
output = output.next
Now that we have the list built with the least significant digits ordered from left to right, let's reverse the ordering.
We will initialize our previous and current nodes to null and the head, respectively. The current head, which will be the tail after we reverse the list, will be the node directly connected to the dummy node.
previous, current = None, dummy.next
While the current pointer isn't at a null node, we continue moving down the list, setting each current pointer's next reference to the previous node.
while current:
At the beginning of each iteration, we will save bridge as the next node.
bridge = current.next
We want to do this because once we overwrite current.next and set it to the previous node, we will lose our bridge to get to the next node.
Once we saved our bridge, we will overwrite the reference to our next node by setting it to the previous node, previous.
current.next = previous
We will then move our previous pointer to the current pointer, and our current pointer will cross the bridge to the next node.
previous = current
current = bridge
Once we have traversed the entire list and reversed each pointer, we will return the previous pointer because the loop broke when the current node reached a null value, so if we were to return it then we would return nothing.
The previous pointer will have stopped at the old tail, which is now the new head.
return previous