You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

 

 

Solution:

Dummy note help to return the result LinkedList.

If the sum of that digit is larger than 10, carry it to the next digit. (check carry after finish two input LinkedList)

Using while loop to adding two LinkedList, before each of them has next value.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode l3 = dummyHead;
        int carry = 0;
        
        while (l1 != null && l2 != null) {
            int sum = (l1.val + l2.val + carry) % 10;
            carry = (l1.val + l2.val + carry) / 10;
            ListNode curVal = new ListNode(sum);
            l3.next = curVal;
            l3 = l3.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        while (l1 != null) {
            int sum = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;
            ListNode curVal = new ListNode(sum);
            l3.next = curVal;
            l3 = l3.next;
            l1 = l1.next;
        }
        
        while (l2 != null) {
            int sum = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;
            ListNode curVal = new ListNode(sum);
            l3.next = curVal;
            l3 = l3.next;
            l2 = l2.next;
        }
        
        if (carry > 0) {
            ListNode curVal = new ListNode(carry);
            l3.next = curVal;
            l3 = l3.next;
        }
        
        return dummyHead.next;
    }
}

 

Time complexity: O(max(m, n))

Space complexity: O(max(m, n))