2. Add Two Numbers - Detailed Explanation

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, meaning that the 1’s digit is at the head of the list. 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. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Examples

Example 1

• Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
• Explanation: The numbers represented are 342 and 465. When added together, 342 + 465 = 807.
• Output: [7, 0, 8]
  (The linked list [7, 0, 8] represents 807 in reverse order.)

Example 2

• Input: l1 = [0], l2 = [0]
• Output: [0]
• Explanation: The sum is 0.

Example 3

• Input: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
• Explanation: The numbers represented are 9,999,999 and 9,999. Their sum is 10,009,998.
• Output: [8, 9, 9, 9, 0, 0, 0, 1]

Approach

The main idea is to simulate the process of adding two numbers digit by digit, as you would do on paper. Since the linked lists store digits in reverse order, you start from the least significant digit (the head of the list) and move toward the most significant digit.

Steps:

1. Initialize a Dummy Head:
   Create a dummy head for the resulting linked list and a pointer (current) to track the end of the list.

2. Set Up Carry:
   Use a variable (carry) to store any carry-over value during the addition.

3. Traverse Both Linked Lists:

   • Retrieve the digit from each list. If one list is shorter, treat the missing digit as 0.
   • Compute the sum: digit from l1 + digit from l2 + carry.
   • Update the carry for the next iteration (carry = total // 10).
   • Create a new node with the value (total % 10) and attach it to the current node.

4. Handle Remaining Carry:
   After processing both lists, check if there is any remaining carry. If so, add a new node with that carry value.

5. Return the Result:
   Return the node following the dummy head as the head of the resulting linked list.

Step-by-Step Walkthrough

Consider l1 = [2, 4, 3] and l2 = [5, 6, 4]:

• Initialization:
  Create a dummy head node and set the current pointer to the dummy. Initialize carry = 0.

• First Digit Addition:

  • l1: 2, l2: 5
  • Sum = 2 + 5 + 0 = 7
  • Create a node with value 7, set carry to 0.

• Second Digit Addition:

  • l1: 4, l2: 6
  • Sum = 4 + 6 + 0 = 10
  • Create a node with value 0 (10 % 10), update carry to 1.

• Third Digit Addition:

  • l1: 3, l2: 4
  • Sum = 3 + 4 + 1 = 8
  • Create a node with value 8, update carry to 0.

• Final Check:
  Both lists are fully processed and carry is 0, so the final linked list is [7, 0, 8].