Adding Two Numbers: Coding Solutions and FAQs
Here we present solutions in C++, Java, and Python to the problem of adding two numbers.
Problem Statement: Given two non-empty linked lists representing two non-negative integers, add the two numbers and return them as a linked list.
Approach: We will iterate through the linked lists, adding the values of each node together, and creating a new node with the sum of the values. If the sum is greater than 9, we carry the 1 to the next node. If one list is shorter than the other, we substitute 0 for the missing value to continue the summation.
C++ Code:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* res = new ListNode(0);
ListNode* curr = res;
int carry = 0;
while (l1 || l2 || carry) {
int v1 = l1 ? l1->val : 0;
int v2 = l2 ? l2->val : 0;
int sum = v1 + v2 + carry;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return res->next;
}
};
Java Code:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0);
ListNode curr = res;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int v1 = l1 != null ? l1.val : 0;
int v2 = l2 != null ? l2.val : 0;
int sum = v1 + v2 + carry;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
l1 = l1 != null ? l1.next : l1;
l2 = l2 != null ? l2.next : l2;
}
return res.next;
}
}
Python Code:
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
curr = res
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
summ = v1 + v2 + carry
carry = summ // 10
curr.next = ListNode(summ % 10)
curr = curr.next
l1 = l1.next if l1 else l1
l2 = l2.next if l2 else l2
return res.next
FAQs:
- What is the time complexity of this algorithm? The time complexity is O(max(m,n)), where m and n are the lengths of the linked lists representing the two numbers.
- What is the space complexity of this algorithm? The space complexity is also O(max(m,n)), due to the creation of a new linked list to store the result.
- What is a linked list? A linked list is a data structure consisting of a collection of nodes, each containing a value and a reference (or pointer) to the next node in the sequence.
For more information on linked lists and this problem, check out LeetCode.
LinkedList Number Sum
Given two numbers represented as LinkedList, this program finds the sum of two numbers represented as LinkedList.
Sample Test Cases:
TestCase 1:
//First input LinkedList
ListNode firstList = new ListNode(7);
firstList.next = new ListNode(5);
firstList.next.next = new ListNode(9);
firstList.next.next.next = new ListNode(4);
firstList.next.next.next.next = new ListNode(6);
//Second input LinkedList
ListNode secondList = new ListNode(8);
secondList.next = new ListNode(4);
//Expected Output LinkedList
ListNode Result = new ListNode(5);
Result.next = new ListNode(0);
Result.next.next = new ListNode(0);
Result.next.next.next = new ListNode(5);
Result.next.next.next.next = new ListNode(6);
TestCase 2:
//First input LinkedList
ListNode firstList = new ListNode(0);
//Second input LinkedList
ListNode secondList = new ListNode(0);
//Expected Output LinkedList
ListNode Result = new ListNode(0);
Explanation:
In the first test case, firstList = 75946 and secondList = 84. Sum of these numbers results in 50056.
In the second test case, both the lists represent number 0, hence the output is also number 0.
Linked List Traversal for Addition
The following algorithm is used to perform addition on two linked lists:
1. Traverse both linked lists and append zeros to the shorter list until both lists have an equal number of digits.
2. Begin a recursive function at the start nodes of both lists.
3. Recursively move ahead on both lists until the end is reached.
4. Create new nodes during recursion to store the sum of digits, returning the carry to the next node for the sum operation.
Adding Two Numbers as Lists: Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* A, ListNode* B) {
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
int carry = 0;
while(A || B || carry){
int sum = 0;
if(A){
sum += A->val;
A = A->next;
}
if(B){
sum += B->val;
B = B->next;
}
sum += carry;
carry = sum / 10;
current->next = new ListNode(sum % 10);
current = current->next;
}
return dummy->next;
}
};
This solution is for the problem “Add Two Numbers as Lists” and demonstrates how to add two numbers represented as linked lists. The solution iterates over each node in both linked lists and adds their values, accounting for any carried-over digits. The solution is optimized and has clear, concise code with comments.
C++ Code: Summing Two Linked Lists
Here is the C++ code to add two linked lists positon-wise:
Node* addLinkedLists(Node* head1, Node* head2) {
Node* res = NULL;
Node* prev = NULL;
Node* temp;
int carry = 0;
int sum = 0;
while(head1 != NULL || head2 != NULL) {
sum = carry + (head1 ? head1->data : 0) + (head2 ? head2->data : 0);
carry = (sum >= 10) ? 1 : 0;
sum = sum % 10;
temp = newNode(sum);
if(res == NULL) {
res = temp;
} else {
prev->next = temp;
}
prev = temp;
if(head1) {
head1 = head1->next;
}
if(head2) {
head2 = head2->next;
}
}
if(carry > 0) {
temp->next = newNode(carry);
}
return res;
}
Node* reverseList(Node* head) {
if(head == NULL || head->next == NULL) {
return head;
}
Node* rest = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
Node* sumLinkedLists(Node* list1, Node* list2) {
list1 = reverseList(list1);
list2 = reverseList(list2);
Node* added = addLinkedLists(list1, list2);
return reverseList(added);
}
The addLinkedLists function adds two linked lists that have integer digits in each location and returns the resultant list. The reverseList function reverses the linked list and returns the reversed linked list. The sumLinkedLists function reverses the two linked lists, adds them position-wise, and reverses the resultant linked list.
Adding Two Linked Lists
public static Node addLists(Node first, Node second) {
// create new nodes with value 0 before the first node of each list
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
// add preceding zeros if one list is longer than the other
addPrecedingZeros(start1, start2);
// set up result node and perform addition until end of both nodes
Node result = new Node(0);
if (sumNodes(start1.next, start2.next, result) == 1) {
Node dummy = new Node(1);
dummy.next = result.next;
result.next = dummy;
}
return result.next;
}
// perform two-node addition recursively and return carry
public static int sumNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int sum = 0;
sum += first.data;
sum += second.data;
sum += sumNodes(first.next, second.next, result);
Node dummy = new Node(sum % 10);
dummy.next = result.next;
result.next = dummy;
return sum / 10;
}
// add preceding zeros to the shorter list
public static void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null) {
while (next2 != null) {
Node dummy = new Node(0);
dummy.next = start1.next;
start1.next = dummy;
next2 = next2.next;
}
} else if (next2 == null) {
while (next1 != null) {
Node dummy = new Node(0);
dummy.next = start2.next;
start2.next = dummy;
next1 = next1.next;
}
}
}
public static Node addTwoLists(Node a, Node b) {
return solve(a, b);
}
public static Node solve(Node first, Node second) {
return addLists(first, second);
}
This code adds two linked lists node-by-node, carrying over any sum greater than 9 to the next calculation. It ensures that both lists are of equal length by adding preceding zeros to the beginning of the shorter list. The final result is returned as a new linked list. Test cases and exceptions should be added to this code as necessary.
Addition of two Linked Lists
class Node:
def __init__(self, data):
self.data = data
self.next = None
def addLinkedLists(first, second):
# Initialize variables to keep track of linked lists given as input,
# results of addition, the "carry" digit, and the position in the list.
prev, temp = None, None
carry = 0
while first is not None or second is not None:
# Handle cases where one list could be shorter than the other.
if first is None:
firstData = 0
else:
firstData = first.data
if second is None:
secondData = 0
else:
secondData = second.data
Sum = carry + firstData + secondData
carry = 1 if Sum >= 10 else 0
Sum %= 10
temp = Node(Sum)
# Store addition results in a temporary linked list.
if prev is None:
head = temp
else:
prev.next = temp
prev = temp
# Position to next node in each linked list.
if first is not None:
first = first.next
if second is not None:
second = second.next
# Add final carry if there is one.
if carry > 0:
temp.next = Node(carry)
# Return head node of result linked list.
return head
The given code performs the addition of two linked lists in linear time and space complexity. The updated function is optimized and assumes the input are valid linked lists
FAQs
Q. Why are zeros added to the end of the shorter linked list?
A. Zeros are added to the end of the linked list to aid implementation of the problem logic. This is equivalent to adding zeros before a number and does not change the value of the list.
Q. How is the carry calculated for the addition of digits?
A. The carry is calculated for the sum of digits using the following rule: “If the sum of digits exceeds 10, the carry is 1, else it is 0.”
function addLinkedLists(l1, l2) {
//logic for adding linked lists here
}
Additional Resources
Explore more about Linked Lists:
//Detect Loop in Linked List
//Reverse a Linked List
//Delete Node in a Linked List
//Intersection of Two Linked Lists
//Linked List Interview Questions
//Linked List MCQ
//Application of Linked List
//Types of Linked List
