leetcode

Add Two Numbers solution using TypeScript

Below is my TypeScript solution to the LeetCode "Add Two Numbers" question using a recursive approach.

Time Complexity: The time complexity of this algorithm will be O(max(m, n)) because it will recursively call the add function once per node in the first or second list, whichever is longer.

Space Complexity: The space complexity will also be O(max(m, n)) because the length of the returned list will be, at most, the length of the longer inputted lists + 1.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 * Add Two numbers represented by a Singly Linked List and
 * return the sum as a new Singly Linked List
 *
 *   Time Complexity: O(max(m, n))
 *   Space Complexity: O(max(m, n))
 *
 *   Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 *   Output: 7 -> 0 -> 8
 *   Explanation: 342 + 465 = 807.
 */
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    return add(l1, l2, 0);

    // helper function that allows us to pass a carried value on recursive calls
    function add(l1: ListNode | null, l2: ListNode | null, carried: number): ListNode | null {
        const value1 = l1 && l1.val || 0;
        const value2 = l2 && l2.val || 0;
        const sum = value1 + value2 + carried;
        const carry = Math.floor(sum / 10);

        if (l1 || l2 || carried) {
            // LeetCode won't allow the creation of a new ListNode instance so return an object
            return { 
                val: sum % 10, 
                next: add(
                    l1 && l1.next, 
                    l2 && l2.next, 
                    carry) 
            }
        }
        return null;
    }
}

more LeetCode posts