SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

When given two linked lists representing two non-negative integers where the digits are stored in reverse order, the problem essentially asks us to add these two numbers digit by digit. This is similar to how you would perform addition manually, starting from the least significant digit (rightmost digit) to the most significant digit (leftmost digit). As we traverse the linked lists, we keep track of the carry that results from the sum of the digits at each position.

Approach

1. Initialization:

   • Create a dummy node to act as the head of the result linked list. This simplifies the logic for appending new nodes.
   • Use a current pointer to build the result list.
   • Initialize a carry variable to 0 to handle the carry-over in the sum.

2. Traverse the Linked Lists:

   • Loop through both linked lists until both are exhausted (i.e., both are None).
   • For each iteration, get the current digit from both linked lists. If a linked list is exhausted, use 0 as the current digit.
   • Compute the sum of the current digits along with the carry.
   • Update the carry for the next iteration (carry = sum // 10).
   • Create a new node with the digit (sum % 10) and append it to the result list.

3. Handle Remaining Carry:

   • After the loop, if there is any carry left, create a new node with the carry value and append it to the result list.

4. Return Result:

   • Return the next node of the dummy node, as the dummy node was just a placeholder.

Complexity

Time Complexity:

O(max(m, n)), where m and n are the lengths of the two linked lists. We traverse both linked lists once.

Space Complexity:

O(max(m, n)), which is the space required for the result linked list. This does not include the space required for the input linked lists.

Code

C++

/**
 * 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 = new ListNode(0);
        ListNode* current = dummy;
        int carry = 0;

        while (l1 != nullptr || l2 != nullptr) {
            int val1 = l1 != nullptr ? l1->val : 0;
            int val2 = l2 != nullptr ? l2->val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        if (carry > 0) {
            current->next = new ListNode(carry);
        }
        return dummy->next;
    }
};

Python

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        current = dummy
        carry = 0

        while l1 is not None or l2 is not None:
            val1 = l1.val if l1 is not None else 0
            val2 = l2.val if l2 is not None else 0
            sum = val1 + val2 + carry
            carry = sum // 10
            current.next = ListNode(sum % 10)
            current = current.next
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next

        if carry > 0:
            current.next = ListNode(carry)
        return dummy.next

Java

/**
 * 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(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) {
            current.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

JavaScript

var addTwoNumbers = function (l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    let carry = 0;

    while (l1 !== null || l2 !== null) {
        let val1 = l1 !== null ? l1.val : 0;
        let val2 = l2 !== null ? l2.val : 0;
        let sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (l1 !== null) l1 = l1.next;
        if (l2 !== null) l2 = l2.next;
    }
    if (carry > 0) {
        current.next = new ListNode(carry);
    }

    return dummy.next;
};