Algorithm
The "Add Two Numbers" problem is a classic problem in computer science that involves adding two linked lists representing numbers. The lists are arranged such that each node in the list contains a single digit and the digits are stored in reverse order, such that the least significant digit is at the head of the list.
Here is the problem statement from LeetCode:
https://leetcode.com/problems/add-two-numbers/
Details of Leetcode Add two numbers 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.
Example:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
To solve this problem, you can follow these steps:
- Initialize two pointers
pandqto traverse throughl1andl2, respectively, and a carry variable to keep track of any carry over from the addition of the nodes. - Enter a loop that continues until both
pandqbecomenull, which indicates that we have reached the end of both lists. - Inside the loop, get the values of the nodes pointed to by
pandq, or0if one of the pointers isnull, and add them together along with the carry. - Update the carry and create a new node with the sum modulo
10. - Advance both
pandqto the next node in their respective lists. - After the loop has completed, check if there is still a carry remaining. If so, create a new node for it.
- Return the resulting linked list.
I hope this helps! Let me know if you have any questions.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
/**
* 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) {
let dummyHead = new ListNode(0);
let p = l1, q = l2, curr = dummyHead;
let carry = 0;
while (p != null || q != null) {
let x = (p != null) ? p.val : 0;
let y = (q != null) ? q.val : 0;
let sum = carry + x + y;
carry = Math.floor(sum / 10);
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
};
Input
Output
#2 Code Example with C Programming
Code -
C Programming
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *head = NULL, *tail = NULL;
int carry = 0;
while (l1 != NULL || l2 != NULL || carry != 0) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
carry = sum / 10;
sum %= 10;
struct ListNode *node = malloc(sizeof(struct ListNode));
node->val = sum;
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return head;
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
# 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:
head = tail = ListNode(0)
carry = 0
while l1 or l2 or carry:
sum = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry = sum // 10
tail.next = ListNode(sum % 10)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return head.next
This solution is similar to the one in C, but uses Python's ternary operator and native support for linked lists to simplify the code. It iterates through the two input linked lists and adds their values, storing the carry in a variable and creating a new node for the result linked list with the sum modulo 10. It continues this process until both input lists are exhausted and the carry is 0.
I hope this helps! Let me know if you have any questions. Copy The Code & Try With Live Editor
Input
Output
#4 Code Example with PHP Programming
Code -
PHP Programming
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
function addTwoNumbers($l1, $l2) {
$head = $tail = new ListNode(0);
$carry = 0;
while ($l1 || $l2 || $carry) {
$sum = ($l1 ? $l1->val : 0) + ($l2 ? $l2->val : 0) + $carry;
$carry = intval($sum / 10);
$sum %= 10;
$tail->next = new ListNode($sum);
$tail = $tail->next;
$l1 = $l1 ? $l1->next : null;
$l2 = $l2 ? $l2->next : null;
}
return $head->next;
}
}
This solution is similar to the ones in C and Python, but uses PHP's ternary operator and native support for linked lists to simplify the code. It iterates through the two input linked lists and adds their values, storing the carry in a variable and creating a new node for the result linked list with the sum modulo 10. It continues this process until both input lists are exhausted and the carry is 0.
I hope this helps! Let me know if you have any questions. Copy The Code & Try With Live Editor
Input
Output
#5 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode head(0);
ListNode* cur = &head;
int carry = 0;
while(l1 || l2 || carry){
int x = l1 ? l1->val : 0;
int y = l2 ? l2->val : 0;
ListNode* node = new ListNode((x + y + carry) % 10);
cur->next = node;
cur = node;
carry = (x + y + carry) / 10;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
return head.next;
}
};
Input
Output
#6 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode root = new ListNode(-1);
ListNode curr = root;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int currSum = carry;
if (l1 != null && l2 != null) {
currSum += l1.val + l2.val;
l1 = l1.next;
l2 = l2.next;
} else if (l1 != null && l2 == null) {
currSum += l1.val;
l1 = l1.next;
} else if (l1 == null && l2 != null) {
currSum += l2.val;
l2 = l2.next;
}
carry = currSum > 9 ? 1 : 0;
currSum %= 10;
curr.next = new ListNode(currSum);
curr = curr.next;
}
return root.next;
}
}
Input
Output
#7 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _002_AddTwoNumbers
{
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
var dummy = new ListNode(-1);
var current = dummy;
var carry = 0;
while (l1 != null || l2 != null)
{
var value1 = l1 == null ? 0 : l1.val;
var value2 = l2 == null ? 0 : l2.val;
var sum = value1 + value2 + carry;
carry = sum / 10;
sum %= 10;
current.next = new ListNode(sum);
current = current.next;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
if (carry != 0)
current.next = new ListNode(carry);
return dummy.next;
}
}
}
Input
Output
Demonstration
This solution first initializes a dummy head for the resulting linked list and two pointers p and q to traverse through l1 and l2, respectively. It also initializes a carry variable to keep track of any carry over from the addition of the nodes.
Then, it enters a loop that continues until both p and q become null, which indicates that we have reached the end of both lists. Inside the loop, the solution gets the values of the nodes pointed to by p and q, or 0 if one of the pointers is null, and adds them together along with the carry. It then updates the carry and creates a new node with the sum modulo 10, and advances both p and q to the next node in their respective lists.
Finally, the solution checks if there is still a carry remaining after the loop has completed and, if so, creates a new node for it. It then returns the next node after the dummy head, which is the beginning of the resulting linked list.
I hope this helps! Let me know if you have any questions.
Tags: Leetcode Add two numbers solution in JavaScript, C Programming, PHP, Python