Easy Java Solution with O(1) space complexity and O(n) time Complexity with an detailed explanation


  • 0
    T
         * 1) find the point which the length to the end equals to the shorter one:
         *      A->B->C->D and B->D :the point is C in the first list
         * 2) calculate recursively for the common area :C->D and B->D;
         * 3) get the carry bit of the first calculate : sum;
         * 4) calculate recursively for the left of the longer list;
         * 5) return the longer list, we record the num in the longer list
         *
         * */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if (l1 == null && l2 == null) return null;
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    
            //node[1]: the point which th plus begain;
            //node[0]: the head of the long list;
            ListNode[] node = findPosition(l1, l2);
            
            if (node[1] == l2) {
                int sum = calculate(l1, l2);
                if (sum == 1) {
                    ListNode head = new ListNode(1);
                    head.next = l1;
                    return head;
                }
                return l1;
            }else {
                if (node[0] == l1) {
                    int sum = calculate(node[1], l2);
                    if (sum == 0) return l1;
                    if (calculate(l1, sum, node[1]) == 1) {
                        ListNode head = new ListNode(1);
                        head.next = l1;
                        return head;
                    }
                    return l1;
                }else {
                    int sum = calculate(node[1], l1);
                    if (sum == 0) return l2;
                    if (calculate(l2, sum, node[1]) == 1) {
                        ListNode head = new ListNode(1);
                        head.next = l2;
                        return head;
                    }
                    return l2;
                }
            }
        }
       
        //calculate one
        private int calculate(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return 0;
            }
            int sum = l1.val + l2.val + calculate(l1.next, l2.next);
            l1.val = sum%10;
            sum = sum >= 10 ? 1:0;
            return sum;
        }
        //calculate two
        private int calculate(ListNode l1, int sum, ListNode node) {
            if (l1 == node) {
                return sum;
            }
            sum = l1.val + calculate(l1.next, sum, node) ;
            if (sum == 0) return 0;
            l1.val = sum%10;
            sum = sum >= 10? 1:0;
            return sum;
        }
    
        //find point
        private ListNode[] findPosition(ListNode l1, ListNode l2) {
            ListNode t1 = l1;
            ListNode t2 = l2;
            ListNode[] tag = new ListNode[2];
            while (t1.next != null && t2.next != null) {
                t1 = t1.next;
                t2 = t2.next;
            }
            //1) l1 is as long as l2 
            //2)l1 is longer
            //3)l2 is longer
            if (t1.next == null && t2.next == null) {
                tag[0] = l1;
                tag[1] = l2;
            }else if (t1.next == null) {
                solve (tag, l2, t2);
            }else {
                solve (tag, l1, t1);
            }
            return tag;
        }
        //find the point using former and latter pointer
        private void solve(ListNode[] tag, ListNode l, ListNode t) {
            tag[0] = l;
            ListNode p = l;
            while (t.next != null) {
                p = p.next;
                t = t.next;
            }
            tag[1] = p;
        }
    

Log in to reply
 

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