Add Two Numbers medium

Problem Statement

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.

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2

Input: l1 = [0], l2 = [0] Output: [0]

Steps

1. Initialization: Create a dummy head node for the result linked list. This simplifies handling the first node. Initialize a carry variable to 0.
2. Iteration: Iterate through both linked lists simultaneously using two pointers, p and q. In each iteration:
   • Calculate the sum of the digits at the current nodes (p.val and q.val) plus the carry.
   • Update the carry to the quotient of the sum divided by 10 (integer division).
   • Create a new node with the remainder of the sum divided by 10 (the units digit) and append it to the result list.
   • Move pointers p and q to the next nodes.
3. Handle Remaining Nodes: If one list is longer than the other, continue iterating through the remaining nodes of the longer list, adding the carry.
4. Handle Final Carry: If there's a remaining carry after processing all nodes, append a new node with the carry value.
5. Return: Return the next node after the dummy head (the actual head of the result list).

Explanation

The algorithm simulates addition as we do it manually. We process digits from least significant to most significant (because the lists are reversed). The carry variable keeps track of any overflow from the sum of digits. The dummy node simplifies the code by handling edge cases where the result list starts empty.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // Dummy node for simplification
        ListNode current = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10; //integer division
            int digit = sum % 10; //remainder

            current.next = new ListNode(digit);
            current = current.next;
        }

        return dummyHead.next;
    }
}

Complexity

• Time Complexity: O(max(m, n)), where m and n are the lengths of the input linked lists. We iterate through the lists once.
• Space Complexity: O(max(m, n)), in the worst case, the result list will have a length equal to the maximum of the lengths of the input lists plus one (for the carry). This space is used for the new linked list.