Sunday, December 3, 2023
HomeDSASolving Leetcode 2. Add Two Numbers

# Solving Leetcode 2. Add Two Numbers

From Leetcode.

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.

– We are given two non-empty linked lists representing two non-negative integers.

– The digits are stored in reverse order and each of the linked list’s nodes contain a single digit.

– We need to add the two numbers and return it as a linked list.

– We may assume that the two numbers do not contain any leading zero, except for the number 0 itself.

## What is the question (Leetcode 2) asking?

To give you an example, given the two linked lists: 7->1->6 + 5->9->2 The sum is: 7->1->6->9 Explanation: 342 + 295 = 637.

## How would you solve this problem?

There are many ways to solve this problem. One way would be to iterate through both lists, adding the values of each node together. If the sum of the two nodes is greater than 10, you would need to carry over the 1 to the next node. Another way to solve this problem would be to convert both linked lists into integers, add the integers together, and then convert the sum into a linked list.

The most optimal solution depends on the situation. If the linked lists are very long, it may be more efficient to convert them into integers and add the integers together. This is because adding two integers is a relatively simple operation, and it would avoid having to iterate through a long linked list. If the linked lists are not very long, it may be more efficient to iterate through both lists, adding the values of each node together. This is because iterating through a linked list is a relatively simple operation, and it would avoid having to convert the linked lists into integers.

I prefer the solution of iterating through both lists, adding the values of each node together. I prefer this solution because it is a relatively simple operation, and it would avoid having to convert the linked lists into integers.

## Leetcode 2 Code solution.

Here is the code in JavaScript

```var addTwoNumbers = function(l1, l2) {
// create a new linked list to store the sum
let sumList = new ListNode(0);
let current = sumList;

// create a carryover variable to keep track of values >= 10
let carryover = 0;

// iterate through both lists, adding the values of each node together
while (l1 || l2) {

// get the values of the current nodes in each list
let val1 = l1 ? l1.val : 0;
let val2 = l2 ? l2.val : 0;

// add the values together, plus any carryover from the previous sum
let sum = val1 + val2 + carryover;

// if the sum is >= 10, set the carryover to 1
if (sum >= 10) {
carryover = 1;
} else {
// otherwise, reset the carryover to 0
carryover = 0;
}

// create a new node with the sum (minus any carryover)
let newNode = new ListNode(sum % 10);

// set the current node's next value to the new node, and advance the current node
current.next = newNode;
current = newNode;

// advance l1 and l2 to the next nodes
if (l1) {
l1 = l1.next;
}
if (l2) {
l2 = l2.next;
}
}

// if there is a carryover after iterating through both lists, add a new node with the carryover
if (carryover === 1) {
let newNode = new ListNode(1);
current.next = newNode;
}

// return the sum list
return sumList.next;

};```

The time complexity is O(n), where n is the length of the longer linked list. The space complexity is O(n), where n is the length of the sum linked list.

The most optimal solution to this problem depends on the situation. If the linked lists are very long, it may be more efficient to convert them into integers and add the integers together. However, if the linked lists are not very long, it may be more efficient to iterate through both lists, adding the values of each node together. Above we showed the solution of iterating through both lists, adding the values of each node together, this is the simple operation, and we avoided having to convert the linked lists into integers.

RELATED ARTICLES