all articles

leetcode war 2 - Add Two Numbers

2016-09-17 @sunderls

leetCode

following solutions are all created by myself, if I didn't tackle it and got solution from editorial solution, it will be made clear at the heading.

leetcode war: Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

You are given two linked lists representing two non-negative numbers.
The digits are stored in reverse order and each of their nodes contain a single digit.
Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

solution 1 - just traverse the two list simultaneously

Not very difficult I think, attention to the add curry and the last carry.

var addTwoNumbers = function(l1, l2) {
    var result = null;
    var start1 = l1;
    var start2 = l2;
    var start3 = null;
    var carry = 0;

    while(start1 !== null || start2 !== null){
        var val = carry;

        if (start1 !== null){
            val += start1.val;
        }

        if (start2 !== null){
            val += start2.val;
        }
        carry = val > 9 ? 1 : 0;
        val %= 10;

        var newNode = new ListNode(val);
        if (start3 === null){
            result = newNode;
            start3 = newNode;
        } else {
            start3.next = newNode;
            start3 = newNode;
        }

        if (start1 !== null){
           start1 = start1.next;         
        }

        if (start2 !== null){
            start2 = start2.next;           
        }
    }

    // when it ends, we check the carry
    if (carry){
        start3.next = new ListNode(1);
    }

    return result;
};

This is at O(n), 216 ms got. is there any other way? seems not.

Editorial Solution

The solution is almost the same, except my answer can be improved by removing the start3 comparison. I focused on returning the result directly, in fact I can initialize result to a node and return the next node. It reduced time to 188 ms;

var addTwoNumbers = function(l1, l2) {
    var result = new ListNode(0);
    var start1 = l1;
    var start2 = l2;
    var start3 = result;
    var carry = 0;

    while(start1 !== null || start2 !== null){
        var val = carry;

        if (start1 !== null){
            val += start1.val;
        }

        if (start2 !== null){
            val += start2.val;
        }
        carry = val > 9 ? 1 : 0;
        val %= 10;

        var newNode = new ListNode(val);
        start3.next = newNode;
        start3 = start3.next

        if (start1 !== null){
           start1 = start1.next;         
        }

        if (start2 !== null){
            start2 = start2.next;           
        }
    }

    // when it ends, we check the carry
    if (carry){
        start3.next = new ListNode(1);
    }

    return result.next;
};