Add Two Numbers

class Solution {
public:
    ListNode* sumTwoLists(ListNode* first, ListNode* second) {
        ListNode* start = new ListNode(0);
        ListNode* pointer = start;
        int excess = 0;
        while (first != NULL || second != NULL || excess != 0) {
            int val1 = first ? first->val : 0;
            int val2 = second ? second->val : 0;
            int total = excess + val1 + val2;
            excess = total / 10;
            pointer->next = new ListNode(total % 10);
            pointer = pointer->next;
            first = first ? first->next : nullptr;
            second = second ? second->next : nullptr;
        }
        ListNode* resultHead = start->next;
        delete start;  
        return resultHead;
    }
};

The provided C++ code defines a method named sumTwoLists within a class Solution. This method takes two input nodes (representing two non-empty linked lists) and returns a new linked list representing the sum of the two numbers. Each linked list contains integers in reverse order, where each node contains a single digit.

Here's an overview of the steps involved in the solution:

1. Initialize a sentinel node start with zero value to simplify result handling. Use a pointer to manage the current position in the resulting linked list.

2. Maintain a variable excess to handle carry over when the sum of two digits exceeds 9.

3. Loop through the nodes of both linked lists until both are exhausted and there's no carry remaining (excess is zero). In each iteration:

   • Extract values from the current nodes of both lists, defaulting to 0 if the node is null.
   • Compute the total of excess, val1, and val2.
   • Calculate the new digit to store (from the total) and update excess for the next iteration.
   • Move to the next node in both input linked lists if available.

4. After exiting the loop, clean up the initial sentinel node to avoid memory leaks and return the start of the resulting linked list.

The code ensures that the time complexity is linear with respect to the number of digits in the larger number, and the function efficiently handles carry over between digits in a clean and readable manner. By using a sentinel node, edge cases around list initialization and single-node results are neatly managed, simplifying linking logic.

class Solution {
    public ListNode sumLists(ListNode list1, ListNode list2) {
        ListNode headNode = new ListNode(0);
        ListNode pointer = headNode;
        int overflow = 0;
        while (list1 != null || list2 != null || overflow != 0) {
            int val1 = (list1 != null) ? list1.val : 0;
            int val2 = (list2 != null) ? list2.val : 0;
            int total = overflow + val1 + val2;
            overflow = total / 10;
            pointer.next = new ListNode(total % 10);
            pointer = pointer.next;
            if (list1 != null) list1 = list1.next;
            if (list2 != null) list2 = list2.next;
        }
        return headNode.next;
    }
}

The provided code defines a class Solution with a method sumLists(ListNode list1, ListNode list2) that adds two numbers represented as linked lists. Each node in the linked list represents a single digit and digits are stored in reverse order. Here's how the function works:

• Initialize a new empty head node, headNode, with a value of 0 to hold the result.
• Use a pointer, which starts at headNode, to add nodes for the result.
• Use an integer, overflow, to handle any overflow (carry bit) while summing each digit.
• Iterate through each node of list1 and list2:
  • Extract values from current nodes of list1 and list2 if they exist; otherwise, use 0.
  • Calculate the sum of these values and the overflow.
  • Update overflow to hold any carry from the sum.
  • Create a new node with the digit part of the sum (i.e., total % 10) and attach it to pointer.
  • Move the pointer and input list nodes (list1 and list2) to the next nodes.
• When all nodes are processed including the last carry, return the result starting from next to the dummy head node (headNode.next).

This approach efficiently processes the digits and carries in a space-efficient manner with linear time complexity relative to the number of digits in the longer list.

struct ListNode* sumTwoNumbers(struct ListNode* first, struct ListNode* second) {
    struct ListNode* tempHead = malloc(sizeof(struct ListNode));
    tempHead->val = 0;
    tempHead->next = NULL;
    struct ListNode* temp = tempHead;
    int overflow = 0;
    while (first != NULL || second != NULL || overflow != 0) {
        int num1 = (first != NULL) ? first->val : 0;
        int num2 = (second != NULL) ? second->val : 0;
        int total = overflow + num1 + num2;
        overflow = total / 10;
        temp->next = malloc(sizeof(struct ListNode));
        temp->next->val = total % 10;
        temp->next->next = NULL;
        temp = temp->next;
        if (first != NULL) first = first->next;
        if (second != NULL) second = second->next;
    }
    struct ListNode* finalResult = tempHead->next;
    free(tempHead);
    return finalResult;
}

The function sumTwoNumbers in C efficiently adds two numbers represented by linked lists where each node contains a single digit. Here's an overview of how the function achieves this:

1. Initializes a temporary dummy head node for the resultant linked list to handle the sums conveniently. The pointer temp is used to add new nodes to this list.
2. Uses a variable overflow to keep track of the carry-over during addition.
3. Iterates through each node of the two input lists, first and second. If one list is shorter, it treats missing nodes as having a value of 0.
4. During each iteration, calculates the sum of the two digits (and any existing carry-over). The carry-over for the next position is determined by dividing the current sum by 10.
5. A new node is then created for the resultant linked list with the digit part total % 10.
6. Upon completing the iterations through both lists, it handles any leftover carry-over by potentially adding an extra node.
7. Finally, frees the dummy node originally created and returns the next node which is the head of the resultant list, thus ensuring efficient memory use.

This solution efficiently handles different lengths of input lists and considers the possible carry-over at each step of the addition, making it robust for large numbers.

var sumLists = function (first, second) {
    let tempHead = new ListNode(0);
    let pointer = tempHead;
    let overflow = 0;
    while (first !== null || second !== null || overflow !== 0) {
        let val1 = first !== null ? first.val : 0;
        let val2 = second !== null ? second.val : 0;
        let sumValue = overflow + val1 + val2;
        overflow = Math.floor(sumValue / 10);
        pointer.next = new ListNode(sumValue % 10);
        pointer = pointer.next;
        if (first !== null) first = first.next;
        if (second !== null) second = second.next;
    }
    return tempHead.next;
};

The JavaScript function sumLists takes two linked lists (first and second), which represent two non-negative integers. The digits are stored in reverse order, and each node of the linked list contains a single digit. The function adds the two numbers and returns the sum as a linked list in the same reversed order.

• Initialize tempHead with a new ListNode of value 0. This acts as a dummy node to simplify list manipulation.
• Start with pointer pointing to tempHead which helps in building the resulting linked list.
• Use overflow to handle the carry generated during sum computation.
• Iterate through first and second lists. If the current node is null in any list, assume its value as 0.
• Calculate sumValue for the current position by summing up val1, val2, and overflow.
• Update overflow with the carryover value, which is the integer division of sumValue by 10.
• Update the next node of pointer with a new ListNode with the unit digit of sumValue.
• Move the pointer to the next node.
• Navigate first and second to their next nodes respectively if they are not null.
• Upon completing the iterations, return tempHead.next, which points to the head of the resultant linked list excluding the initial dummy node.

This implementation efficiently handles lists of different lengths and possible extra carry that may require extending the resultant list's length beyond the input lists.

class Solution:
    def sumTwoLists(
        self, first: Optional[ListNode], second: Optional[ListNode]
    ) -> Optional[ListNode]:
        tempHead = ListNode(0)
        pointer = tempHead
        overflow = 0
        while first is not None or second is not None or overflow:
            firstVal = first.val if first else 0
            secondVal = second.val if second else 0
            total = firstVal + secondVal + overflow
            overflow = total // 10
            nextNode = ListNode(total % 10)
            pointer.next = nextNode
            pointer = nextNode
            first = first.next if first else None
            second = second.next if second else None
        return tempHead.next

The provided solution outlines a method to sum two numbers represented as linked lists, where each node represents a single digit and the digits are stored in reverse order. Here is a breakdown of the solution:

• Define a class Solution with a method sumTwoLists that accepts two linked lists: first and second.
• Initialize a placeholder linked list using tempHead = ListNode(0) and a pointer to traverse this list.
• Set an overflow variable to handle the carry-over during addition.
• Loop through the nodes of both lists until all elements are processed, including the last overflow:
  • Calculate the value for each node from the sum of the corresponding nodes in the input lists and any overflow.
  • Determine the new overflow and the digit to store in the current node.
  • Move to the next nodes in the input lists if they exist.
• Return the next node of tempHead as the head of the result linked list, effectively skipping the placeholder node.

This approach effectively handles the addition of the numbers in a digit-wise manner while managing carry-over between digits, and returns the sum as a new linked list. No auxiliary space other than the space needed for the result is used, and the solution traverses each list only once, ensuring efficiency.