In the LeetCode Problem #2, we are given two numbers, with each digit represented in a node of the linked lists in reversed order. The task is to find the sum of those numbers and return the result in the form of a linked list again in reversed order.
For example; if the inputs are [1,2,3] and [4,5,6] then the actual numbers would be 321 and 654; their sum would be 975 and we should return a linked list [5,7,9]. We're given some constraints.
- All the numbers would be non-negative numbers.
- There won't be leading zeros; which means inputs won't have a digit
0 at the head of the lists.
- The number of nodes in each of the lists would be from 1 to 100.
- And finally, the values in each of the nodes will range from 0 to 9.
Solution
The solution for this problem is straightforward; we can traverse through the linked lists and then construct the original numbers. For example, if our list is [1,2,3] then we can construct our original number 321 with a simple logic as used in the pseudocode below.
function findReverseNumber(headNode *LinkNode):
originalNum := 0
node := headNode
while(node neq null) {
originalNum = originalNum*10 + node.value
node = node.next()
}
return originalNum
end function
Now we can modify this pseudocode to simultaneously traverse through both lists and get two numbers in one go. Then we can sum up two numbers to get our results. We can use modulo division to reverse the number and construct our final linked list. Finally, we will return the head node.
function addTwoNumbers(headNode1, headNode2 *LinkNode):
originalNum1 := 0
originalNum1 := 0
node_1 := headNode1
noide_2 := headNode2
// traversing through two nodes
while(node_1 neq null or node_2 neq null) {
if (node_1 neq null){
originalNum1 = originalNum1*10 + node_1.value
node_1 = node_1.next()
}
if (node_2 neq null){
originalNum2 = originalNum2*10 + node_2.value
node_2 = node_2.next()
}
}
sum := originalNum1 + originalNum2
digit := sum %10
head := ListNode
head.value = digit
head.next = null
sum = (sum - digit) / 10
nextNode = head
while (sum / 10 neq 0) {
newNode := ListNode
digit := sum %10
sum = (sum - digit) / 10
newNode.value = digit
nextNode.next = newNode
nextNode = newNode
}
return head
end function
The solution above has O(2n), where n = max(list1.length, list2.length); time complexity. While implementing this logic in GO lang, we will have to take care of one more problem; the length of the lists. They could go up to 100 nodes in length; which means in our approach of generating the original number from the linked list using number = number*10 + node.value can create a huge intermediate number of order 10100. To mitigate this, we can use the big library package available with go installation. The complete solution to this problem in the go programming language is as below.
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
sumOfFirstNode := big.NewInt(0)
sumOfSecondNode := big.NewInt(0)
mul := big.NewInt(1)
ten := big.NewInt(10)
for {
if l1 == nil && l2 == nil {
break
}
if l1 != nil {
sumOfFirstNode = big.NewInt(0).Add(big.NewInt(0).Mul(mul, big.NewInt(int64(l1.Val))), sumOfFirstNode)
l1 = l1.Next
}
if l2 != nil {
sumOfSecondNode = big.NewInt(0).Add(big.NewInt(0).Mul(big.NewInt(int64(l2.Val)), mul), sumOfSecondNode)
l2 = l2.Next
}
mul = big.NewInt(0).Mul(mul, big.NewInt(10))
}
sum := big.NewInt(0).Add(sumOfFirstNode, sumOfSecondNode)
modTen := big.NewInt(0).Mod(sum, ten)
node := &ListNode{
Val: int(modTen.Int64()),
Next: nil,
}
nextNode := node
sum = big.NewInt(0).Div(big.NewInt(0).Sub(sum, modTen), ten)
for sum.Cmp(big.NewInt(0)) > 0 {
modTen := big.NewInt(0).Mod(sum, ten)
nextNode.Next = &ListNode{
Val: int(modTen.Int64()),
Next: nil,
}
sum = big.NewInt(0).Div(big.NewInt(0).Sub(sum, modTen), ten)
nextNode = nextNode.Next
}
return node
}
Although, this solution is pretty efficient and works well; still there is some space for improvement. One clean approach is to generate our result linked-list while traversing the input lists. It will create an efficient solution with O(n) time complexity and remove some intermediate calculations. It will also prevent the usage of big library because summing up two single-digit numbers results in a double-digit number at max. The implementation of the new solution is left for the readers to complete.
