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:
- We first define a
ListNode
class to represent each node in the linked list. - We define the
addTwoNumbers
function that takes two linked lists as input and returns the sum as a linked list. - We create a
dummy_head
node to keep track of the head of the new linked list. - We initialize a
current_node
variable to thedummy_head
and acarry
variable to 0. - We loop through the linked lists as long as
l1
orl2
orcarry
is not None. - We get the values of the current nodes in
l1
andl2
(or 0 if the nodes are None), add them together with thecarry
, and store the result incurrent_sum
. - We update the
carry
variable with the integer division ofcurrent_sum
by 10 (since we are dealing with base-10 numbers), and updatecurrent_node
to a new node with the value of the remainder ofcurrent_sum
by 10 (since that is the digit in the ones place). - We update
l1
andl2
to their next nodes (or None if they are already at the end of the linked list). - We return the
next
node of thedummy_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:
- We first define a
ListNode
class to represent each node in the linked list. - We define the
add_two_numbers
function that takes two linked lists as input and returns the sum as a linked list. - We create a
dummy_head
node to keep track of the head of the new linked list. - We initialize a
current_node
variable to thedummy_head
and acarry
variable to 0. - We loop through the linked lists as long as
l1
orl2
orcarry
is not positive. - We get the values of the current nodes in
l1
andl2
(or 0 if the nodes are nil), add them together with thecarry
, and store the result incurrent_sum
. - We update the
carry
variable with the integer division ofcurrent_sum
by 10 (since we are dealing with base-10 numbers), and updatecurrent_node
to a new node with the value of the remainder ofcurrent_sum
by 10 (since that is the digit in the ones place). - We update
l1
andl2
to their next nodes (or nil if they are already at the end of the linked list). - We return the
next
node of thedummy_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:
- We first define a
ListNode
class to represent each node in the linked list. - We define the
addTwoNumbers
function that takes two linked lists as input and returns the sum as a linked list. - We create a
dummyHead
node to keep track of the head of the new linked list. - We initialize a
currentNode
variable to thedummyHead
and acarry
variable to 0. - We loop through the linked lists as long as
l1
orl2
orcarry
is not 0. - We get the values of the current nodes in
l1
andl2
(or 0 if the nodes are null), add them together with thecarry
, and store the result incurrentSum
. - We update the
carry
variable with the integer division ofcurrentSum
by 10 (since we are dealing with base-10 numbers), and updatecurrentNode
to a new node with the value of the remainder ofcurrentSum
by 10 (since that is the digit in the ones place). - We update
l1
andl2
to their next nodes (or null if they are already at the end of the linked list). - We return the
next
node of thedummyHead
, 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:
- We define the
ListNode
class using the constructor function syntax, with properties forval
andnext
. - We define the
addTwoNumbers
function using thevar
keyword, which takes two linked lists as input and returns the sum as a linked list. - We create a
dummyHead
node using thenew
keyword to keep track of the head of the new linked list. - We initialize a
currentNode
variable to thedummyHead
and acarry
variable to 0. - We loop through the linked lists as long as
l1
orl2
orcarry
is not 0. - We get the values of the current nodes in
l1
andl2
(or 0 if the nodes are null), add them together with thecarry
, and store the result incurrentSum
. - We update the
carry
variable with the integer division ofcurrentSum
by 10 (since we are dealing with base-10 numbers), and updatecurrentNode
to a new node with the value of the remainder ofcurrentSum
by 10 (since that is the digit in the ones place). - We update
l1
andl2
to their next nodes (or null if they are already at the end of the linked list). - We return the
next
node of thedummyHead
, 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.