Add Two Numbers in Linked Lists with Digits in Reverse Order

95.2k
0

Given the heads of two singly linked lists representing two non-negative integers, add the numbers and return the sum as a new linked list. Each node stores one digit, and digits appear in reverse order, so the head node stores the unit digit.

Example 1

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]

Output: [7, 0, 8]

Explanation: Stored numbers are 342 and 465. Sum equals 807, so reverse-order list becomes [7, 0, 8].

Example 2

Input: l1 = [9, 9, 9], l2 = [1]

Output: [0, 0, 0, 1]

Explanation: Stored numbers are 999 and 1. Repeated carry creates one extra node at the end.

Brute Force Approach

A beginner-friendly flow separates the task into two parts. First, one straight traversal collects digits from the first list into one array and digits from the second list into another array. Second, another loop walks through both arrays position by position, adds matching digits, and builds the answer list from generated sum digits.

Algorithm

  • Initialize two arrays to store the digits from both linked lists, as keeping the digits separately makes position-wise addition straightforward.

  • Traverse the first linked list and push every node value into the first array, so all digits of the first number are available by index.

  • Traverse the second linked list and push every node value into the second array, giving the same positional access for the second number.

  • Initialize indices for both arrays, along with carry and dummy-tail pointers for the answer list, as these are needed to track the current digits, carry-forward value, and result construction.

  • Run a loop while either array still has an unprocessed digit or carry is non-zero, since the remaining carry can itself produce an additional digit.

  • Add the current digits and carry, where missing digits are treated as 0, because the two linked lists may represent numbers of different lengths.

  • Create a new node using sum % 10, as this gives the digit that belongs at the current position, and update carry using sum / 10 for the next position.

  • Attach the new node at the tail of the answer list and move the required indices and pointers forward, so the next pair of digits can be processed.

  • Return dummy.next as the head of the final sum list, since the dummy node only helps simplify construction and is not part of the answer.

Dry Run

add two number ll1

add two number ll1

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode* next;
ListNode(int data) {
val = data;
next = nullptr;
}
};
class Solution {
public:
// Add two numbers by collecting digits first and addition later.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// Store digits from the first linked list.
vector<int> firstDigits;
// Store digits from the second linked list.
vector<int> secondDigits;
// Traverse the first list and collect every digit.
while (l1 != nullptr) {
firstDigits.push_back(l1->val);
l1 = l1->next;
}
// Traverse the second list and collect every digit.
while (l2 != nullptr) {
secondDigits.push_back(l2->val);
l2 = l2->next;
}
// Dummy node helps in easy answer-list construction.
ListNode* dummy = new ListNode(0);
// Tail always points to the last node of the answer list.
ListNode* tail = dummy;
// Indices walk through stored digits.
int i = 0;
int j = 0;
// Carry stores overflow from the previous digit sum.
int carry = 0;
// Continue until both arrays and carry become empty.
while (i < (int)firstDigits.size() || j < (int)secondDigits.size() || carry > 0) {
// Start current sum with carry value.
int sum = carry;
// Add the current digit from the first array when available.
if (i < (int)firstDigits.size()) {
sum += firstDigits[i];
i++;
}
// Add the current digit from the second array when available.
if (j < (int)secondDigits.size()) {
sum += secondDigits[j];
j++;
}
// Current node stores the unit digit.
int digit = sum % 10;
// Carry moves to the next position.
carry = sum / 10;
// Create the next answer node.
tail->next = new ListNode(digit);
// Advance tail after node attachment.
tail = tail->next;
}
// Return the real head after skipping the dummy node.
return dummy->next;
}
};
// Build a linked list from a digit array.
ListNode* buildList(const vector<int>& values) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy->next;
}
// Print the linked list in a readable format.
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val;
if (head->next != nullptr) {
cout << " ";
}
head = head->next;
}
cout << "\n";
}
// Run the brute-force style solution on a hard-coded sample.
int main() {
vector<int> first = {2, 4, 3};
vector<int> second = {5, 6, 4};
ListNode* l1 = buildList(first);
ListNode* l2 = buildList(second);

Complexity Analysis

Time Complexity: O(N + M), one traversal collects digits and one loop builds the answer list.

Space Complexity: O(N + M), extra arrays store digits before sum construction.

Optimal Approach

The most natural linked-list solution walks through both chains together and adds digits on the fly. One loop handles three moving parts at once: the current node from the first list, the current node from the second list, and the carry from the previous sum. Every loop iteration creates exactly one answer node, so construction stays clean and direct.

Algorithm

  • Initialize a dummy node, a tail pointer, and carry as 0, where the dummy node simplifies result construction and tail keeps track of the last node in the answer list.

  • Traverse while the first list has nodes, the second list has nodes, or carry is non-zero, since the addition must continue until every digit and the final carry have been processed.

  • Read the current digit from each list when a node exists and use 0 when a list has already ended, as the two numbers may have different lengths.

  • Add both digits along with carry to form the sum for the current position, since the carry from the previous position contributes to the current digit.

  • Create a new node using sum % 10, as this gives the digit that belongs at the current position, and attach it after tail.

  • Update carry using sum / 10, as the quotient represents the value that needs to be carried to the next position.

  • Advance the tail and list pointers after processing the current digits, so the next iteration works with the next position in both numbers.

  • Return dummy.next as the head of the sum list, since the dummy node is only used to simplify the linked-list construction.

Dry Run

add two ll 2

add two ll 2

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int val;
ListNode* next;
ListNode(int data) {
val = data;
next = nullptr;
}
};
class Solution {
public:
// Function to add two numbers.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// Dummy node simplifies answer-list construction.
ListNode* dummy = new ListNode(0);
// Tail always marks the last answer node.
ListNode* tail = dummy;
// Carry stores overflow from the previous digit sum.
int carry = 0;
// Continue until both lists end and carry becomes zero.
while (l1 != nullptr || l2 != nullptr || carry > 0) {
// Start current sum with the carry value.
int sum = carry;
// Add the current digit from the first list when available.
if (l1 != nullptr) {
sum += l1->val;
l1 = l1->next;
}
// Add the current digit from the second list when available.
if (l2 != nullptr) {
sum += l2->val;
l2 = l2->next;
}
// Current node stores the unit digit.
int digit = sum % 10;
// Carry moves to the next position.
carry = sum / 10;
// Attach a new node with the current digit.
tail->next = new ListNode(digit);
// Move tail to the newly created node.
tail = tail->next;
}
// Return the real head after skipping the dummy node.
return dummy->next;
}
};
// Build a linked list from a digit array.
ListNode* buildList(const vector<int>& values) {
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy->next;
}
// Print the linked list in a readable format.
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val;
if (head->next != nullptr) {
cout << " ";
}
head = head->next;
}
cout << "\n";
}
// Run the optimal solution on a hard-coded sample.
int main() {
vector<int> first = {9, 9, 9};
vector<int> second = {1};
ListNode* l1 = buildList(first);
ListNode* l2 = buildList(second);
Solution solution;
ListNode* answer = solution.addTwoNumbers(l1, l2);
printList(answer);
return 0;
}

Complexity Analysis

Time Complexity: O(max(N, M)), one traversal loop processes both lists together.

Space Complexity: O(1), auxiliary memory stays constant apart from the returned answer list.

Interview follow-up Questions

Reverse-order storage places the unit digit at the head, so matching place values appear in the same traversal direction.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.8k
Linked List

Sort a Linked List Using Merge Sort

Given the head of a singly linked list, sort the linked list in non-decreasing order and return the head of the sorted linked list. Each node contains an integer value and a pointer to the next nod...

112.1k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order...

101.5k
Comments0