Sum two numbers represented as Linked Lists

Technology CommunityCategory: Linked ListsSum two numbers represented as Linked Lists
VietMX Staff asked 3 years ago
Problem

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.

You can add two numbers represented using LinkedLists in the same way you add two numbers by hand.

Iterate over the linked lists, add their corresponding elements, keep a carry just the way you do while adding numbers by hand, add the carry-over from the previous addition to the current sum and so on.

One of the trickiest parts of this problem is the issue of the carried number – if every pair of nodes added to a number less than 10, then there wouldn’t be a concern of ‘carrying’ digits over to the next node. However, adding numbers like 4 and 6 produces a carry.

If one list is longer than the other, we still will want to add the longer list’s nodes to the solution, so we’ll have to make sure we continue to check so long as the nodes aren’t null. That means the while loop should keep going as long as list 1 isn’t null OR list 2 isn’t null.

Implementation
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode result = head;
    int carry = 0;
    
    while (l1 != null || l2 != null || carry > 0) {
        int resVal = (l1 != null? l1.val : 0) + (l2 != null? l2.val : 0) + carry;
        result.next = new ListNode(resVal % 10);
        carry = resVal / 10;
        l1 = (l1 == null ? l1 : l1.next);
        l2 = (l2 == null ? l2 : l2.next);
        result = result.next;
    }
    
    return head.next;
}