Java O(n) time, O(1) space


  • 0
    Y

    If input list modifications are allowed, this can be done without extra space.

     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode cur = l1, prev = l1;
            int sum = 0;
            while(cur != null || l2 !=null){
                sum /= 10;
                if(cur != null){
                    sum += cur.val;
                }else{
                    cur = prev;
                    cur.next = l2;
                    cur = cur.next;
                    sum += cur.val;
                    l2 = null;
                }
                if(l2 != null){
                    sum += l2.val;
                    l2 = l2.next;
                }
                if(cur != null){
                    cur.val = sum%10;
                    prev = cur;
                    cur = cur.next;
                }
            }
            if(sum > 9)
              prev.next = new ListNode(1);  
            return l1;
        }
    

Log in to reply
 

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