Adding LinkedList elements Kotlin solution- LeetCode #1
Tags: algorithms, programming, kotlin
Published: 2021-05-12 14:22:02

Problem definition is also available [here](https://leetcode.com/problems/add-two-numbers).



**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

1. [seed0.value] + 1 + 9 computed and divided by 10

2. Remainder updated to seed0#value

3. Seed1 created with quotient as the value

4. Seed1 placed as seed0.next

5. 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

1. L1 is null now, p2 = 9 and seed1 = 1 so sum is 10. Which is again divided by 10.
2. Remainder is updated to seed1#value 
3. Seed2 created takes the carry(1)
4. Seed1#next points to seed2
5. Over to next pass [L1.next, L2.next, seed2]



```
pass-2
            [1]  	      // seed2
     1  ==            1
    99  ==      9  ←  9
    00  ==      0  ←  0    
```



1. L1 = null, p2 = null, seed2 = 1.  sum is 1 now.
2. Remainder updated in seed2
3. 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.



```kotlin
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)
            }
        }
    }
}
```