Add Two Numbers

Problem Statement

LeetCode-2: 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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

Approach

We can solve this problem using a simple iterative approach for traversing linked lists.

1. As the input lists are already sorted in reverse order, we will iterate over both linked lists and keep adding the values of the nodes.
2. We will also keep track of the carry.
3. And finally, we will create a new linked list and keep adding the sum of the nodes to the new linked list. We will return the new linked list as the result.

Implementation

Here is a Java implementation of the above approach:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode itr = dummy;
    int carry = 0;

    while (l1 != null || l2 != null) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        
        int sum = carry + x + y;
        carry = sum / 10;
        itr.next = new ListNode(sum % 10);
        itr = itr.next;
    
        if (l1 != null){
            l1 = l1.next;
        }
    
        if (l2 != null){
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        itr.next = new ListNode(carry);
    }
    return dummy.next;
}

Complexity Analysis

The time complexity for this approach is $O(max(m, n))$, where $m$ and $n$ are the lengths of the two linked lists.