Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            total = v1 + v2 + carry
            carry = total // 10
            current.next = ListNode(total % 10)
            current = current.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

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

// Definition for singly-linked list.
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(0);
        ListNode current = 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;
            current.next = new ListNode(total % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;
    while (l1 || l2 || carry) {
        let v1 = l1 ? l1.val : 0;
        let v2 = l2 ? l2.val : 0;
        let total = v1 + v2 + carry;
        carry = Math.floor(total / 10);
        current.next = new ListNode(total % 10);
        current = current.next;
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }
    return dummy.next;
};
      

Problem Description

You are given two non-empty singly linked lists, l1 and l2, that represent two non-negative integers. The digits are stored in reverse order, and each node contains a single digit.
Your task is to add the two numbers and return the sum as a linked list, also in reverse order.

• Each input list represents a non-negative integer, with the 1's digit at the head of the list.
• You may assume the two numbers do not contain any leading zeros, except the number 0 itself.
• The two numbers can be of different lengths.
• There will always be one valid solution.
• You must not modify the input lists (i.e., do not reuse the nodes in l1 or l2).

Example:
l1 = [2,4,3] (represents 342)
l2 = [5,6,4] (represents 465)
Output: [7,0,8] (represents 807)

Thought Process

At first glance, this problem looks like elementary addition, but with the numbers stored "backwards" in linked lists. The challenge is to add digit by digit, handling carry-overs, and produce a new linked list as the result.

A brute-force approach might involve converting the linked lists into integers, adding them, and then converting the sum back into a linked list. However, this does not work for very large numbers that cannot fit into standard integer types.

Instead, we need to simulate the addition process as we would do by hand: add corresponding digits, keep track of the carry, and move through the lists node by node. This way, we avoid integer overflow and stay within the constraints of the problem.

The process is similar to adding two numbers column by column, from right to left (which is head to tail in the list, since the digits are reversed).

Solution Approach

Let's break down the solution step by step:

1. Initialize:
   • Create a dummy head node for the result linked list. This simplifies handling the head of the result and makes code cleaner.
   • Use a pointer current to build the new list, and a variable carry to store the carry-over during addition (start at 0).
2. Iterate:
   • Loop as long as at least one of l1, l2, or carry is non-zero.
   • At each step, extract the current digit from l1 and l2 (use 0 if the list is exhausted).
   • Add the two digits and the carry.
   • The new digit is (sum) % 10, and the new carry is (sum) // 10.
   • Create a new node for the digit and append it to the result list.
   • Advance l1 and l2 as needed.
3. Finish:
   • When the loop ends, the result list is complete. Return dummy.next (skip the dummy node).

Why use a dummy node? It helps avoid special cases for the head of the list, making it easier to append new nodes.

Example Walkthrough

Let's walk through the example l1 = [2,4,3] and l2 = [5,6,4]:

• Step 1: Add 2 (from l1) + 5 (from l2) + 0 (carry) = 7
  Place 7 in the new list. Carry = 0.
• Step 2: Add 4 (from l1) + 6 (from l2) + 0 (carry) = 10
  Place 0 in the new list. Carry = 1.
• Step 3: Add 3 (from l1) + 4 (from l2) + 1 (carry) = 8
  Place 8 in the new list. Carry = 0.
• Both lists are now exhausted, and carry is 0, so we stop.

The final linked list is [7,0,8], which represents the number 807.

Time and Space Complexity

• Brute-force Approach:
  Converting lists to numbers and back would be O(N+M) for list traversal, but integer conversion could be problematic for very large numbers.
• Optimized Approach:
  - Time Complexity: O(max(N, M)), where N and M are the lengths of l1 and l2. Each node is processed exactly once.
  - Space Complexity: O(max(N, M)), since we create a new list for the result. No extra data structures are used except a few variables.

The optimized approach is efficient for very large numbers, as it never converts the whole number to an integer.

Summary

The "Add Two Numbers" problem is a great example of simulating elementary addition using linked lists. By processing each digit node-by-node, handling carry-overs, and building a new result list, we avoid integer overflow and keep the solution efficient. Using a dummy node simplifies result list construction, and the algorithm is both straightforward and robust, scaling to arbitrarily large numbers.