Algorithm-Day28-Add-Two-Numbers-lc-2

Posted on In , Views:

🧩 Problem Description

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each node 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
2
3
4
5
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

Explanation:
342 + 465 = 807

💡 Intuition

  • Since the numbers are stored in reverse, we can simulate digit-by-digit addition like grade school.
  • Maintain a carry variable for overflow.
  • Traverse both lists and construct the result list.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);  // Dummy head
        ListNode curr = dummy;
        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;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }

        return dummy.next;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(max(n, m)) — traverses both lists once
  • Space Complexity: O(max(n, m)) — result list size

✍️ Summary

  • This is a classic linked list and math simulation problem.
  • Be comfortable managing carry and dummy nodes.
  • Appears frequently in interviews and serves as a great test of logic + list handling.

For follow-ups, consider:

  • BigInteger usage (if languages allow)
  • Lists in forward order (lc-445)