DEV Community

Mahendran
Mahendran

Posted on

Adding LinkedList elements Kotlin solution- LeetCode #1

#algorithms #programming #kotlin

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  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
Enter fullscreen mode Exit fullscreen mode

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) } } } }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)