LeetCode 445. Add Two Numbers II

LeetCode Notes [57]: Easy O(n) Kotlin Solution using Stack

渚橋

Problem

Add Two Numbers II - LeetCode

Intuition

Use Stack to reverse the order of two lists, and then perform addition.

Code

class Solution {
        fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        val s1 = Stack<Int>()
        val s2 = Stack<Int>()

        var pointer = l1
        while (pointer != null) {
            s1.push(pointer.`val`)
            pointer = pointer.next
        }

        pointer = l2
        while (pointer != null) {
            s2.push(pointer.`val`)
            pointer = pointer.next
        }

        val root = ListNode(0)
        pointer = root
        var carry = 0
        while (s1.isNotEmpty() || s2.isNotEmpty() || carry>0) {
            val num1 = if (s1.isNotEmpty()) s1.pop() else 0
            val num2 = if (s2.isNotEmpty()) s2.pop() else 0
            val sum = num1 + num2 + carry
            pointer!!.`val` = sum % 10
            val node = ListNode(0)
            node.next = pointer
            carry = sum / 10
            pointer = node
        }
        return pointer!!.next
    }
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)