C++ solution: linear time and O(1) space except answer itself (32ms, non-recursive)


  • 2

    Not sure if anyone got the same idea, but doesn't seem to appear in some top voted posts.

    The "frontier" pointer stands for the nodes (possibly) impacted by carry and nearest to the list head. And "head" node is more like a helper node storing the carry propagated to the head.

        int count(ListNode* n) {
            int ret =0 ;
            while(n) ++ret, n = n->next;
            return ret;
        }
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int c1 = count(l1), c2 = count(l2);
            if(c1 > c2) swap(c1,c2), swap(l1,l2);
            ListNode head(0);
            ListNode *n = &head, *frontier = &head;
            for(int i=0;i<c2-c1;++i, l2 = l2->next) {
                n = n->next = new ListNode(l2->val);
                if(n->val < 9) frontier = n;
            }
            for(;l1;l1 = l1->next, l2 = l2->next) {
                n = n->next = new ListNode(l1->val + l2->val);
                if(n->val < 9) frontier = n;
                else if(n->val > 9) {
                    frontier->val +=1;
                    frontier = frontier->next;
                    while(frontier != n) {
                        frontier->val = 0;
                        frontier = frontier->next;
                    }
                    n->val -= 10;
                }
            }
            if(head.val) {
                ListNode* n2 = new ListNode(1);
                n2->next = head.next;
                n = n2;
            } else n = head.next;
            return n;
        }
    

  • 0
    L

    Nice solution.A good understand of the how add's carry that causes chain carry. But
    jade86's answer, add the corresponding digit, and put the least significant to the first,
    the most to the last, then deal with carry, then reverse the list is better to understand
    and write.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.