My Simple O(n) Java Solution with Comments


  • 0
    Y
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);    // empty header;
        ListNode resCur = head;
        ListNode cursor1 = l1;
        ListNode cursor2 = l2;
        
        int carry = 0;
        int digit = 0;
        while(cursor1 != null || cursor2 != null)
        {
            int sum = 0;
            int val1 = 0;
            int val2 = 0;
            if (cursor1 != null)
                val1 = cursor1.val;
            if (cursor2 != null)
                val2 = cursor2.val;
            sum = val1 + val2 + carry;
            
            carry = sum / 10;
            digit = sum % 10;
            resCur.next = new ListNode(digit);
            
            // advance to next digit
            resCur = resCur.next;
            if (cursor1 != null)
                cursor1 = cursor1.next;
            if (cursor2 != null)
                cursor2 = cursor2.next;
        }
        
        // process the last carry
    	if (carry != 0)
    	{
    		resCur.next = new ListNode(carry);
    	}
        
        return head.next;
    }

  • 3
    Z

    Both "/" and "%" are complex operation which consume more time, you could use substract operation to determine your "carry" and "digit".

    if(sum > 10){ carry = 1; digit = sum - 10;}else{ carry = 0; digit = sum;}

Log in to reply
 

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