Given two non-empty linked lists l1 and l2 which represent two non-negative integers.
The digits are stored in reverse order with each node storing one digit.
Add two numbers and return the sum as a linked list.
Input: l1 = head -> 5 -> 4, l2 = head -> 4
Output: head -> 9 -> 4
Explanation: l1 = 45, l2 = 4.
l1 + l2 = 45 + 4 = 49.
Input: l1 = head -> 4 -> 5 -> 6, l2 = head -> 1 -> 2 -> 3
Output: head -> 5 -> 7 -> 9
Explanation: l1 = 654, l2 = 321.
l1 + l2 = 654 + 321 = 975.
Input: l1 = head -> 1, l2 = head -> 8 -> 7
Imagine you have two numbers written on paper, with the digits arranged backward:
Number 1: 3 -> 2 -> 1 (Represents 123)
Number 2: 4 -> 5 -> 6 (Represents 654)
To add them, you'd start from the rightmost digits (ones place), add them up (1 + 4 = 5), then move left to the next pair (tens place: 2 + 5 = 7), and so on. If the sum of two digits is greater than or equal to 10, you'd carry over the '1' to the next digit position.
In this problem, the numbers are stored in linked lists, which are essentially chains of nodes, each holding a single digit. The linked lists are in reverse order, just like our example.
Simultaneous Traversal: Traverse both linked lists at the same time, node by node.
Digit-wise Addition: At each step, add the values stored in the current nodes from both lists. Also, add any carry-over from the previous addition.
Create New Node: Calculate the result digit by taking the modulo 10 of the sum. Create a new node to store this digit.
Carry Over: If the sum is 10 or greater, carry over the '1' to the next addition.
Update Pointers: Move the pointers of both lists to their next nodes, and the pointer of the result list to the newly created node.
Continue: Repeat steps 2-5 until you reach the end of both input lists. If there's a carry-over at the end, create one more node for it.
Note that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head's value.
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int data1) {
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1) {
val = data1;
next = next1;
}
};
class Solution {
public:
//Function to add two numbers as linked list
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
/*Dummy node to act as the
starting point of the result list*/
ListNode *dummy = new ListNode();
/*Temp pointer to build
the result list*/
ListNode *temp = dummy;
//Initialize carry
int carry = 0;
/*Iterate while there are nodes in l1 or l2,
or there's a carry to process*/
while ((l1 != NULL || l2 != NULL) || carry) {
int sum = 0;
/*Add the value from l1
if available*/
if (l1 != NULL) {
sum += l1->val;
l1 = l1->next;
}
/*Add the value from l2
if available*/
if (l2 != NULL) {
sum += l2->val;
l2 = l2->next;
}
//Add the carry
sum += carry;
//Update the carry
carry = sum / 10;
/* Create a new node with the digit value
and attach it to the result list*/
ListNode *node = new ListNode(sum % 10);
temp->next = node;
/*Move to the
next position in the result list*/
temp = temp->next;
}
/*Return the result list
skipping the dummy node*/
return dummy->next;
}
};
// Function to print the linked list
void printList(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
//Manual creation of linked list
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
//Instance of solution class
Solution solution;
ListNode* result = solution.addTwoNumbers(l1, l2);
// Print the result
printList(result);
return 0;
}import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to add two numbers as linked list
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
/* Dummy node to act as the
starting point of the result list */
ListNode dummy = new ListNode(0);
/* Temp pointer to build
the result list */
ListNode temp = dummy;
// Initialize carry
int carry = 0;
/* Iterate while there are nodes in l1 or l2,
or there's a carry to process */
while (l1 != null || l2 != null || carry != 0) {
int sum = 0;
/* Add the value from l1
if available */
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
/* Add the value from l2
if available */
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
// Add the carry
sum += carry;
// Update the carry
carry = sum / 10;
/* Create a new node with the digit value
and attach it to the result list */
ListNode node = new ListNode(sum % 10);
temp.next = node;
/* Move to the
next position in the result list */
temp = temp.next;
}
/* Return the result list
skipping the dummy node */
return dummy.next;
}
}
// Function to print the linked list
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Manual creation of linked list
ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
// Instance of solution class
Solution solution = new Solution();
ListNode result = solution.addTwoNumbers(l1, l2);
// Print the result
printList(result);
}
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to add two numbers as linked list
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# Dummy node to act as the starting point of the result list
dummy = ListNode(0)
# Temp pointer to build the result list
temp = dummy
# Initialize carry
carry = 0
# Iterate while there are nodes in l1 or l2, or there's a carry to process
while l1 or l2 or carry:
sum = 0
# Add the value from l1 if available
if l1:
sum += l1.val
l1 = l1.next
# Add the value from l2 if available
if l2:
sum += l2.val
l2 = l2.next
# Add the carry
sum += carry
# Update the carry
carry = sum // 10
# Create a new node with the digit value and attach it to the result list
node = ListNode(sum % 10)
temp.next = node
# Move to the next position in the result list
temp = temp.next
# Return the result list skipping the dummy node
return dummy.next
# Function to print the linked list
def printList(head: ListNode):
while head:
print(head.val, end=" ")
head = head.next
print()
if __name__ == "__main__":
# Manual creation of linked list
l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))
# Instance of solution class
solution = Solution()
result = solution.addTwoNumbers(l1, l2)
# Print the result
printList(result)
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to add two numbers as linked list
addTwoNumbers(l1, l2) {
/* Dummy node to act as the
starting point of the result list */
let dummy = new ListNode(0);
/* Temp pointer to build
the result list */
let temp = dummy;
// Initialize carry
let carry = 0;
/* Iterate while there are nodes in l1 or l2,
or there's a carry to process */
while (l1 !== null || l2 !== null || carry !== 0) {
let sum = 0;
/* Add the value from l1
if available */
if (l1 !== null) {
sum += l1.val;
l1 = l1.next;
}
/* Add the value from l2
if available */
if (l2 !== null) {
sum += l2.val;
l2 = l2.next;
}
// Add the carry
sum += carry;
// Update the carry
carry = Math.floor(sum / 10);
/* Create a new node with the digit value
and attach it to the result list */
let node = new ListNode(sum % 10);
temp.next = node;
/* Move to the
next position in the result list */
temp = temp.next;
}
/* Return the result list
skipping the dummy node */
return dummy.next;
}
}
// Function to print the linked list
function printList(head) {
let current = head;
while (current !== null) {
process.stdout.write(current.val + " ");
current = current.next;
}
console.log();
}
const l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
const l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
const solution = new Solution();
const result = solution.addTwoNumbers(l1, l2);
printList(result);
Q: Why can we process digits directly without reversing the lists?
A: The digits are already in reverse order, so addition naturally starts from the least significant digit (1s place).
Q: How do we handle carry propagation?
A: Maintain a carry variable to track carry-over from the previous sum. If carry > 0 after processing all nodes, add a new node with value carry.
Q: How would this approach change if the digits were stored in forward order instead?
A: Reverse both lists first, then apply the same approach. Alternatively, use recursion with backtracking.
Q: Can we modify this to support subtraction instead of addition?
A: Yes, implement borrow handling instead of carry propagation.