O(N) time O(1) space Java easy to understand with comments.


  • 0
    D

    This is my O(n) time O(1) space self explanatory length based solution.

    public class Solution {
        private static int cntr;
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            cntr = 0;
            ListNode t1 = l1;
            ListNode t2 = l2;
            int cnt1=0;
            int cnt2=0;
            
            //count the lengths of the two numbers/Singly-LL
            while(l1.next != null) {
                l1 = l1.next;
                cnt1++;
            }
            while(l2.next != null) {
                l2 = l2.next;
                cnt2++;
            }
            
            ListNode n = new ListNode(0);
            
            //pass the difference in lengths to helper function
            //helper function will use the difference count to left-align both lists, before recursively travering them until end
            if(cnt1 >= cnt2) {
                n = helper(t1, t2, cnt1-cnt2);
            } else {
                n = helper(t2, t1, cnt2-cnt1);
            }
            
            //n points to the head of result LL
            
            //if n is more than one digit, add another Node (as head) and break up n
            //return new head
            if(n.val > 9) {
                ListNode t = new ListNode(0);
                t.val = (int)(n.val/10);
                n.val = n.val%10;
                t.next = n;
                return t;
            } else {
                return n;
            }
        }
        
        private ListNode helper(ListNode l1, ListNode l2, int x) {
            ListNode r = null;
            ListNode n = new ListNode(0);
            
            //repeat until cntr matches third parameter of helper method (i.e., the difference in lengths)
            //recursively call helper with appropriate arguments
            if(cntr == x && l1.next != null && l2.next != null) {
                cntr++;
                r = helper(l1.next, l2.next, cntr);
                
                n.next = r;
                n.val = l1.val+l2.val+(int)(r.val/10);
                r.val = r.val%10;
                
                return n;
            
            //..increment the l1 pointer till it syncs with head of l2
            } else if(cntr != x) {
                cntr++;
                r = helper(l1.next, l2, x);
                
                n.next = r;
                n.val = l1.val+(int)(r.val/10);
                r.val = r.val%10;
                
                return n;
            } else {
                n.next = r;
                
                n.val = l1.val+l2.val;
                
                return n;
            }
        }
    }
    

Log in to reply
 

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