package dev.egonr.leetcode

/* Medium
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, 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 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]



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

class AddTwoNumbers {
    class ListNode(var `val`: Int) {
        companion object {
            fun fromList(list: List<Int>): ListNode {
                val root = ListNode(list.first())
                var nextNode = root
                list.forEachIndexed { i, it ->
                    if (i > 0) {
                        val newNode = ListNode(it)
                        nextNode.next = newNode
                        nextNode = newNode
                    }
                }
                return root
            }
        }

        var next: ListNode? = null

        override fun toString(): String {
            var res = this.`val`.toString()
            var next: ListNode? = next
            while (next != null) {
                res += next.`val`.toString()
                next = next.next
            }
            return res
        }
    }

    fun test() {
        var n1 = ListNode.fromList(arrayListOf(2, 4, 3))
        var n2 = ListNode.fromList(arrayListOf(5, 6, 4))
        println("$n1 + $n2 = ${addTwoNumbers(n1, n2)}")

        n1 = ListNode.fromList(arrayListOf(5, 5))
        n2 = ListNode.fromList(arrayListOf(5, 5))
        println("$n1 + $n2 = ${addTwoNumbers(n1, n2)}")

        n1 = ListNode.fromList(arrayListOf(9, 9, 9, 9))
        n2 = ListNode.fromList(arrayListOf(9, 9, 9, 9, 9, 9, 9))
        println("$n1 + $n2 = ${addTwoNumbers(n1, n2)}")
    }

    fun ListNode.depth(): Int {
        var depth = 0
        var next: ListNode? = this.next
        while (next != null) {
            depth++
            next = next.next
        }
        return depth
    }

    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        if (l1 == null || l2 == null) {
            return null
        }

        var carry = false
        val l1depth = l1.depth()
        val l2depth = l2.depth()
        val minDepth = Math.min(l1depth, l2depth)
        val maxDepth = Math.max(l1depth, l2depth)
        var nextLong = l1
        var nextShort = l2

        if (l1depth < l2depth) {
            nextLong = l2
            nextShort = l1
        }

        var resultRoot: ListNode? = null
        var resultNext: ListNode? = null
        var loopDepth = 0
        while (nextLong != null) {
            var sum = nextLong!!.`val`
            if (loopDepth <= minDepth) {
                sum += nextShort!!.`val`
                nextShort = nextShort?.next
            }

            if (carry) {
                sum += 1
                carry = false
            }
            if (sum >= 10) {
                sum -= 10
                carry = true
            }

            nextLong = nextLong?.next
            loopDepth++

            if (resultRoot == null) {
                resultRoot = ListNode(sum)
                resultNext = resultRoot
            } else {
                resultNext?.next = ListNode(sum)
                resultNext = resultNext?.next
            }
        }

        if (carry) {
            resultNext?.next = ListNode(1)
        }

        return resultRoot
    }
}