Add two numbers forming linked list : Interview coding problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

The problem requires us to add two numbers represented as linked lists, with each digit in the number stored in a separate node in reverse order.

We can approach this problem by creating a new linked list to represent the sum of the two numbers, digit by digit. We start by initializing a dummyHead node to keep track of the head of the new linked list. We also initialize a currentNode variable to the dummyHead and a carry variable to 0.

We then traverse the two linked lists at the same time, adding the values of the corresponding nodes together, along with the carry value from the previous addition. We compute the remainder of this sum when divided by 10 (to get the digit in the ones place) and add that value to a new node in the new linked list, updating currentNode to point to this new node. We update the carry variable to the integer division of the sum by 10 (to get the digit in the tens place).

If one linked list is shorter than the other, we assume that the remaining nodes in the longer list have a value of 0. We continue traversing the linked lists until we reach the end of both lists and the carry value is 0.

Finally, we return the next node of the dummyHead, which is the head of the new linked list.

Add two numbers Python solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy_head = ListNode(0)
    current_node = dummy_head
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        current_sum = val1 + val2 + carry
        carry = current_sum // 10
        current_node.next = ListNode(current_sum % 10)
        current_node = current_node.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy_head.next

Explanation:

1. We first define a ListNode class to represent each node in the linked list.
2. We define the addTwoNumbers function that takes two linked lists as input and returns the sum as a linked list.
3. We create a dummy_head node to keep track of the head of the new linked list.
4. We initialize a current_node variable to the dummy_head and a carry variable to 0.
5. We loop through the linked lists as long as l1 or l2 or carry is not None.
6. We get the values of the current nodes in l1 and l2 (or 0 if the nodes are None), add them together with the carry, and store the result in current_sum.
7. We update the carry variable with the integer division of current_sum by 10 (since we are dealing with base-10 numbers), and update current_node to a new node with the value of the remainder of current_sum by 10 (since that is the digit in the ones place).
8. We update l1 and l2 to their next nodes (or None if they are already at the end of the linked list).
9. We return the next node of the dummy_head, which is the head of the new linked list.

Add two numbers Ruby solution

class ListNode
  attr_accessor :val, :next
  def initialize(val = 0, _next = nil)
    @val = val
    @next = _next
  end
end

def add_two_numbers(l1, l2)
  dummy_head = ListNode.new(0)
  current_node = dummy_head
  carry = 0

  while l1 || l2 || carry.positive?
    val1 = l1&.val || 0
    val2 = l2&.val || 0
    current_sum = val1 + val2 + carry
    carry = current_sum / 10
    current_node.next = ListNode.new(current_sum % 10)
    current_node = current_node.next

    l1 = l1&.next
    l2 = l2&.next
  end

  dummy_head.next
end

Explanation:

1. We first define a ListNode class to represent each node in the linked list.
2. We define the add_two_numbers function that takes two linked lists as input and returns the sum as a linked list.
3. We create a dummy_head node to keep track of the head of the new linked list.
4. We initialize a current_node variable to the dummy_head and a carry variable to 0.
5. We loop through the linked lists as long as l1 or l2 or carry is not positive.
6. We get the values of the current nodes in l1 and l2 (or 0 if the nodes are nil), add them together with the carry, and store the result in current_sum.
7. We update the carry variable with the integer division of current_sum by 10 (since we are dealing with base-10 numbers), and update current_node to a new node with the value of the remainder of current_sum by 10 (since that is the digit in the ones place).
8. We update l1 and l2 to their next nodes (or nil if they are already at the end of the linked list).
9. We return the next node of the dummy_head, which is the head of the new linked list.

Add two numbers Java solution

class ListNode {
    int val;
    ListNode next;
    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 dummyHead = new ListNode(0);
        ListNode currentNode = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int currentSum = val1 + val2 + carry;
            carry = currentSum / 10;
            currentNode.next = new ListNode(currentSum % 10);
            currentNode = currentNode.next;

            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }

        return dummyHead.next;
    }
}

Explanation:

1. We first define a ListNode class to represent each node in the linked list.
2. We define the addTwoNumbers function that takes two linked lists as input and returns the sum as a linked list.
3. We create a dummyHead node to keep track of the head of the new linked list.
4. We initialize a currentNode variable to the dummyHead and a carry variable to 0.
5. We loop through the linked lists as long as l1 or l2 or carry is not 0.
6. We get the values of the current nodes in l1 and l2 (or 0 if the nodes are null), add them together with the carry, and store the result in currentSum.
7. We update the carry variable with the integer division of currentSum by 10 (since we are dealing with base-10 numbers), and update currentNode to a new node with the value of the remainder of currentSum by 10 (since that is the digit in the ones place).
8. We update l1 and l2 to their next nodes (or null if they are already at the end of the linked list).
9. We return the next node of the dummyHead, which is the head of the new linked list.

Add two numbers Javascript solution

function ListNode(val) {
    this.val = val;
    this.next = null;
}

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

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

        l1 = (l1 !== null) ? l1.next : null;
        l2 = (l2 !== null) ? l2.next : null;
    }

    return dummyHead.next;
};

Explanation:

1. We define the ListNode class using the constructor function syntax, with properties for val and next.
2. We define the addTwoNumbers function using the var keyword, which takes two linked lists as input and returns the sum as a linked list.
3. We create a dummyHead node using the new keyword to keep track of the head of the new linked list.
4. We initialize a currentNode variable to the dummyHead and a carry variable to 0.
5. We loop through the linked lists as long as l1 or l2 or carry is not 0.
6. We get the values of the current nodes in l1 and l2 (or 0 if the nodes are null), add them together with the carry, and store the result in currentSum.
7. We update the carry variable with the integer division of currentSum by 10 (since we are dealing with base-10 numbers), and update currentNode to a new node with the value of the remainder of currentSum by 10 (since that is the digit in the ones place).
8. We update l1 and l2 to their next nodes (or null if they are already at the end of the linked list).
9. We return the next node of the dummyHead, which is the head of the new linked list.

Note that the JavaScript solution is very similar to the Java solution, but with a different syntax. We use !== instead of != for strict equality comparisons, and we use Math.floor instead of integer division. Other than that, the logic is the same.