Problem definition is also available here.
Problem summary:
- We have two linked lists as input each stored the digits of a number in reverse order
i.e 107 represented as 7 ➝ 0 ➝ 1
- These input numbers, can be of different length
i.e 107 == 7 ➝ 0 ➝ 1
2099 == 9 ➝ 9 ➝ 0 ➝ 2
- The expected output for the above case is in the same manner
2206 == 6 ➝ 0 ➝ 2 ➝ 2
Visualize
Let's rewrite these numbers here and flip the arrows.
107 == 1 ← 0 ← 7
2099 == 2 ← 0 ← 9 ← 9
_______________________
2206 == 2 ← 2 ← 0 ← 6
If you see clearly, that's how we compute sum on a paper. Starting from right, carry over when needed and compute the sum. See this special case where result length exceeds the input.
[1] [1] // carry over
1 == 1
99 == 9 ← 9
100 == 1 ← 0 ← 0
Based on above input, we just have to add one decimal position at a time, and pass the carry to the next decimal position. For result, we have to keep chaining next pointer with new digit.
Am approaching this problem with recursive function and a seed — head node. This node will be used to store carry value. Let's iterate on 1 + 99 and see how it looks.
Initial call made [L1, L2, seed0] // Here L1 & L2 are pointers to the input linked lists.
initial values
[0] // seed0
1 == 1
99 == 9 ← 9
Below operaitions performed here
[seed0.value] + 1 + 9 computed and divided by 10
Remainder updated to seed0#value
Seed1 created with quotient as the value
Seed1 placed as seed0.next
Over to next pass [L1.next, L2.next, seed1]
pass-1
[1] // seed1
1 == 1
99 == 9 ← 9
0 == ← 0
Repeat the same operations here
- L1 is null now, p2 = 9 and seed1 = 1 so sum is 10. Which is again divided by 10.
- Remainder is updated to seed1#value
- Seed2 created takes the carry(1)
- Seed1#next points to seed2
- Over to next pass [L1.next, L2.next, seed2]
pass-2
[1] // seed2
1 == 1
99 == 9 ← 9
00 == 0 ← 0
- L1 = null, p2 = null, seed2 = 1. sum is 1 now.
- Remainder updated in seed2
- There is no carry also L1.next & L2.next is null. So, break the recursion here.
output:
1 == 1
99 == 9 ← 9
________________________
100 == 1 ← 0 ← 0
Solution
Here is my kotlin solution. I added few best-case checks to avoid looping through the linked list.
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
// It is painful to work without an extension
fun ListNode?.valueOrZero() = this?.`val` ?: 0
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
return when {
l1 == null && l2 == null -> null
l1 == null -> l2
l2 == null -> l1
else -> {
val seed = ListNode(0)
sumInternal(l1, l2, seed)
seed
}
}
}
private fun sumInternal(l1: ListNode?, l2: ListNode?, seed: ListNode) {
val current = seed.`val` + l1.valueOrZero() + l2.valueOrZero()
seed.`val` = current % 10
val carry = current / 10
// Whether input list has any more elements
var hasNext = l1?.next != null || l2?.next != null
if (carry > 0 || hasNext) {
// Create & link the carry here
var newNode = ListNode(carry)
seed.next = newNode
// If there is no digits further -- break here
if (hasNext) {
sumInternal(l1?.next, l2?.next, newNode)
}
}
}
}
Top comments (0)