2. Add Two Numbers

 

Simplifying the Addition of Two Numbers Represented by Linked Lists

In the world of coding and algorithms, one interesting problem is adding two numbers represented by linked lists. This classic problem often appears in technical interviews and helps in understanding linked lists and basic arithmetic operations. Today, we'll dive deep into solving this problem using JavaScript.

Problem Description

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. Assume the two numbers do not contain any leading zeros, except the number 0 itself.

Intuition

To solve this problem, we can visualize adding the two numbers digit by digit, starting from the least significant digit (the head of the linked lists). The challenge involves handling the carry from each addition and constructing the resulting linked list accordingly.

Approach

1. Initialize Variables:

   • Create a dummy node head to serve as the starting point of the result list.

   • Use temp as a pointer to construct the result list.

   • Initialize total to store the sum of the corresponding digits and carry.

   • Initialize carry to store the carry from the sum of the digits.

2. Loop Through the Lists:

   • Use a while loop to continue as long as there are nodes in either l1 or l2, or there's a carry to be added.

   • Initialize total with the value of carry.

3. Add Values from l1 and l2:

   • If l1 is not null, add its value to total and move to the next node in l1.

   • Similarly, if l2 is not null, add its value to total and move to the next node in l2.

4. Compute the Digit and Carry:

   • The new digit to be added to the result list is total % 10.

   • Calculate the new carry as Math.floor(total / 10).

5. Add the Digit to the Result List:

   • Create a new node with the value num and attach it to temp.next.

   • Move temp to the next node.

6. Return the Result:

   • Return head.next, which is the actual start of the result list (skipping the dummy node).

Code Implementation

Here's the JavaScript code that accomplishes this:

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val === undefined ? 0 : val);
 *     this.next = (next === undefined ? null : next);
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let head = new ListNode(); // Dummy node
    let temp = head;           // Pointer to build the result list
    let total = 0;             // Total sum of corresponding digits
    let carry = 0;             // Carry from the sum of digits

    while (l1 || l2 || carry) {
        total = carry; // Start with carry from the previous iteration

        if (l1) {
            total += l1.val; // Add value from l1
            l1 = l1.next;    // Move to the next node in l1
        }

        if (l2) {
            total += l2.val; // Add value from l2
            l2 = l2.next;    // Move to the next node in l2
        }

        let num = total % 10; // Current digit
        temp.next = new ListNode(num); // Create new node
        temp = temp.next; // Move to the next node in result

        carry = Math.floor(total / 10); // Calculate carry
    }

    return head.next; // Return the actual start of the result list
};

Complexity Analysis

• Time Complexity: The time complexity is $O(\max (m,n))O(\backslash max(m,\; n))$, where m and n are the lengths of the input linked lists l1 and l2. This is because we process each node exactly once.

• Space Complexity: The space complexity is $O(\max (m,n))O(\backslash max(m,\; n))$ due to the space required to store the result linked list.

Conclusion

This problem elegantly demonstrates the power of linked lists and basic arithmetic operations. By following a structured approach, we can handle the addition digit by digit and correctly manage the carry. This solution is efficient and provides a clear understanding of how to work with linked lists in JavaScript.

Happy coding! 😊 If you have any questions or need further assistance, feel free to ask in the comments.