49ms O(n) time O(1) space solution, easy to understand, no reverse, no stack


  • 0
    E

    The most solutions I saw here use a stack or similar data structure to reverse the calculation order, which is very nice. but that cost O(n) space. So I feel like I need to post my original solution to share with you guys.

    To understand this more easily, you can pull out a piece of paper and try to think how you would do the addition from left to right on the paper.

    The idea is, when doing the calculation from left to right, the overflow (which can only be 1) only affects the nearest non-9 digit to the left. and for the digits in between, they all become 0 because they are all 9.

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // Step 1: count the lengths for both list
            // example: 
            // l1:[3, 0, 8] l2: [9, 7, 2, 9, 2]
            int len1 = 0, len2 = 0;
            for (ListNode node = l1;  node != null; node = node.next)
                len1++;
            for (ListNode node = l2;  node != null; node = node.next)
                len2++;
            
            // Step 2: we are going to work on the longer list
            ListNode longList = l1, shortList = l2;
            int longLen = len1, shortLen = len2;
            if (len1 < len2) {
                longLen = len2;
                shortLen = len1;
                longList = l2;
                shortList = l1;
            }
            // now longList = [9, 7, 2, 9, 2] shortList = [3, 0, 8]
            
            ListNode nHead = new ListNode(0);
            nHead.next = longList;
            longList = nHead; // nHead is the first non-9 node on the left from the current working node.
            
            // Step 3: Align the 2 lists
            ListNode pL = nHead.next, pS = shortList;
            for (int i = longLen; i > shortLen; i--) {
                if (pL.val != 9) nHead = pL;
                pL = pL.next;
            }
            // Now longList = [0 (nHead), 9, 7 (pL), 9, 2]
            //    shortList =               [3 (pS), 0, 8]
            
            // Step 4: just do the addition as how we can do it on the paper
            // After first iteration result would be:
            //  longList = [1, 0, 0 (nHead), 9 (pL), 2]
            // shortList =       [3,         0 (pS), 8]
            
            
            while (pL != null) {
                pL.val += pS.val;
                if (pL.val > 9) {
                    pL.val -= 10;
                    nHead.val += 1;
                    nHead = nHead.next;
                    while (nHead != pL) {
                        nHead.val = 0;
                        nHead = nHead.next; // Remember to move nHead when necessary
                    }
                } else if (pL.val < 9) {
                    nHead = pL; // Remember to move nHead when necessary
                }
                pL = pL.next;
                pS = pS.next;
            }
            
            // Step 5: remove the first 0 if there is any
            return longList.val == 0 ? longList.next : longList;
        }
    }
    

    Sorry for putting all code in one function, but you get the idea.


Log in to reply
 

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