Obsidian Notes

7. Add Two Numbers

5 min read

Description

Add Two Numbers
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]

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Approach

  • Iterate the list with condition discussed below and add elements and carry then update carry and the added number so as to only have ones place
  • Condition used here is such we keep adding till the bigger one gets exhausted and assume zero if the shorter one is zero and the condition is added for carry so as to make sure even after the lists are Iterated there could still be some leftover carry
  • Time:O(n) Space: O(n) - It says m + n check once
  • It’s is easier because it is already in reverse I guess with non reverse we create method to reverse and reverse the lists then find answer in list then reverse it to get the right answer
/**
 * 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 dummy = new ListNode();
        ListNode sum = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int v = v1 + v2 + carry;
            carry = v / 10;
            v = v % 10;
            sum.next = new ListNode(v);
            sum = sum.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;        
        }
 
        return dummy.next;
    }
}

1. The “Naïve Brute Force” (Why it fails)

The intuitive naïve approach converts the linked lists into integers, adds them, and converts the result back into a linked list.

  • Logic:
  1. Iterate l1 and l2 to build integers num1 and num2 (accounting for reversed digits).
  2. Add them: total = num1 + num2.
  3. Convert total back to digits and build a new linked list.
  • Why it Fails: The constraints state lists can have up to 100 nodes. A 100-digit integer causes an integer overflow even with 64-bit integers (long in Java/C++ or 64-bit limits in fixed-size languages).

2. Optimal Solution: Single-Pass Elementary Math

Simulate column-by-column addition using a elementary grade-school addition approach.

Mental Model:

  1. Use a Dummy Head to easily build the output linked list without special edge-case handling for the first node.
  2. Maintain a carry variable (starts at 0).
  3. Loop while **l1 exists OR l2 exists OR carry > 0.
  4. In each step: sum values, calculate digit (sum % 10), update carry (sum / 10), and move pointers forward.
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // Holds reference to start of result
        ListNode curr = dummy;
        int carry = 0;
 
        // Run as long as there are digits left or a remaining carry
        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;                     // New carry for next column
            curr.next = new ListNode(sum % 10);    // Current digit
            curr = curr.next;                      // Advance output pointer
        }
 
        return dummy.next;
    }
}

Complexity & Memory Hook:

  • Time Complexity: — Single loop over the longer list.
  • Space Complexity: — Space used only for the output list.
  • Memory Hook: “Sum = Carry + L1 + L2 Node gets % 10, Carry gets / 10.”

Key Difference: Micro-Improvement

In your solution, naming the pointer ListNode sum can be slightly confusing because sum usually refers to an integer, not a node pointer. Renaming ListNode sum to ListNode curr (or tail) makes it 100% ideal.

Highly Intuitive Version (Your Code Refined)

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
 
        while (l1 != null || l2 != null || carry != 0) {
            int v1 = (l1 != null) ? l1.val : 0;
            int v2 = (l2 != null) ? l2.val : 0;
            
            int total = v1 + v2 + carry;
            carry = total / 10;
            
            curr.next = new ListNode(total % 10);
            curr = curr.next;
            
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
 
        return dummy.next;
    }
}

Backlinks