Description:
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.
Examples:
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]Solution in Python:
To solve this problem, we’ll implement the addTwoNumbers method in the Solution class. The method will add two numbers represented by two linked lists and return the sum as a new linked list. The digits in the linked lists are stored in reverse order, so we’ll add the corresponding digits from the two lists and handle the carry-over for digits that sum to more than 9.
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: ListNode, l2: ListNode) -> ListNode:
# Dummy head for the result linked list
dummy_head = ListNode(0)
current = dummy_head
carry = 0
# Loop through the linked lists l1 and l2
while l1 or l2 or carry:
# Get the values from the current nodes of l1 and l2
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# Calculate the sum and the carry
total = val1 + val2 + carry
carry = total // 10
new_digit = total % 10
# Create a new node with the calculated digit
current.next = ListNode(new_digit)
current = current.next
# Move to the next nodes of l1 and l2
if l1:
l1 = l1.next
if l2:
l2 = l2.next
# Return the result linked list, which is next to the dummy head
return dummy_head.nextExplanation:
- Dummy Head Initialization:
- A dummy head node (
dummy_head) is created to simplify edge cases where the resultant list might be empty initially.
- A dummy head node (
- Carry Initialization:
- A variable
carryis initialized to handle cases where the sum of two digits exceeds 9.
- A variable
- Main Loop:
- The loop runs until all nodes in
l1andl2are processed and there is no carry left. - Inside the loop:
- We retrieve the values from the current nodes of
l1andl2. If a list has been fully traversed, its value is considered 0. - We calculate the sum of these values plus any carry from the previous iteration.
- The new digit to be added to the result list is determined using
total % 10. - The carry for the next iteration is updated using
total // 10. - A new node with the digit
new_digitis created and appended to the result list. - We move the pointers of
l1andl2to their next nodes if they exist.
- We retrieve the values from the current nodes of
- The loop runs until all nodes in
- Final Carry Check:
- After the loop, if there is any remaining carry, it is added as a new node to the result list.
- Return Result:
- The resultant linked list is returned, skipping the dummy head node.
This code effectively handles the addition of two numbers represented as linked lists and ensures correct handling of carry-over between digits.
Solution in Javascript:
JavaScript
// Definition for singly-linked list.
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
// Dummy head for the result linked list
let dummyHead = new ListNode(0);
let current = dummyHead;
let carry = 0;
// Loop through the linked lists l1 and l2
while (l1 !== null || l2 !== null || carry !== 0) {
// Get the values from the current nodes of l1 and l2
let val1 = l1 !== null ? l1.val : 0;
let val2 = l2 !== null ? l2.val : 0;
// Calculate the sum and the carry
let total = val1 + val2 + carry;
carry = Math.floor(total / 10);
let newDigit = total % 10;
// Create a new node with the calculated digit
current.next = new ListNode(newDigit);
current = current.next;
// Move to the next nodes of l1 and l2
if (l1 !== null) l1 = l1.next;
if (l2 !== null) l2 = l2.next;
}
// Return the result linked list, which is next to the dummy head
return dummyHead.next;
};Solution in Java:
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) {
// Initialize a dummy head to simplify the code and a pointer to the current node
ListNode dummyHead = new ListNode(0);
ListNode current = dummyHead;
int carry = 0;
// Traverse both lists
while (l1 != null || l2 != null || carry != 0) {
// Get the values from the current nodes, if available
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
// Calculate the sum of the values and the carry
int sum = val1 + val2 + carry;
// Update the carry for the next iteration
carry = sum / 10;
// Create a new node with the digit value (sum % 10) and move the current pointer
current.next = new ListNode(sum % 10);
current = current.next;
// Move to the next nodes in the input lists, if available
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
// The dummy head's next node is the actual head of the result list
return dummyHead.next;
}
}Solution in C++:
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) {
// Initialize a dummy node to simplify the code
ListNode* dummyHead = new ListNode(0);
ListNode* current = dummyHead;
int carry = 0;
// Traverse both lists
while (l1 != nullptr || l2 != nullptr || carry != 0) {
// Get the values from the current nodes, if available
int val1 = (l1 != nullptr) ? l1->val : 0;
int val2 = (l2 != nullptr) ? l2->val : 0;
// Calculate the sum of the values and the carry
int sum = val1 + val2 + carry;
// Update the carry for the next iteration
carry = sum / 10;
// Create a new node with the digit value (sum % 10) and move the current pointer
current->next = new ListNode(sum % 10);
current = current->next;
// Move to the next nodes in the input lists, if available
if (l1 != nullptr) l1 = l1->next;
if (l2 != nullptr) l2 = l2->next;
}
// The dummy head's next node is the actual head of the result list
ListNode* result = dummyHead->next;
delete dummyHead; // Free the allocated memory for the dummy head
return result;
}
};