O(n) time O(1) space Input intact Java solution


  • 0
    J
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // Foolish way const space and no change on l1 and l2.
            if (l1 == null && l2 == null) return null;
    
            int len1 = 0, len2 = 0;
            ListNode n1 = l1, n2 = l2;
            while (n1 != null) {
                len1 ++;
                n1 = n1.next;
            }
            
            while (n2 != null) {
                len2 ++;
                n2 = n2.next;
            }
            
            if (len1 > len2) { // l1 is always the shorter one.
                n1 = l1; // swap head
                l1 = l2;
                l2 = n1;
                
                int tmp = len1; // swap length
                len1 = len2;
                len2 = tmp;
            }
            
            // Insert extra length
            ListNode dummy = new ListNode(0);
            ListNode cur = null;
            n1 = l2; n2 = l1;
            int diff = len2 - len1;
            while (diff != 0) {
                cur = dummy.next;
                dummy.next = new ListNode(n1.val);
                dummy.next.next = cur;
                n1 = n1.next;
                diff --;
            }
            
            // now n1 and n2 should have equal length;
            while (n1 != null) {
                cur = dummy.next;
                dummy.next = new ListNode(n1.val + n2.val);
                dummy.next.next = cur;
                n1 = n1.next; n2 = n2.next;
            }
            
            ListNode h = dummy.next;
            int c = 0;
            ListNode p = null;
            while (h != null) {
                h.val += c;
                c = h.val / 10;
                h.val = h.val % 10;
                p = h;
                h = h.next;
            }
            if (c == 1) {
                p.next = new ListNode(1);
            }
            
            // reverse
            h = dummy.next;
            p = null;
            while (h != null) {
                if (h.next != null) {
                    n1 = h;
                    n2 = h.next;
                    h = h.next.next;
                    
                    n2.next = n1;
                    n1.next = p;
                    p = n2;
                    
                    if (h == null)
                        return n2;
                } else {
                    h.next = p;
                    return h;
                }
            }
            return null;
        }
    }
    

Log in to reply
 

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