Given the head of two singly linked lists num1 and num2 representing two non-negative integers. The task is to return the head of the linked list representing the sum of these two numbers.
For example, num1 represented by the linked list : 1 -> 9 -> 0, similarly num2 represented by the linked list: 2 -> 5. Sum of these two numbers is represented by 2 -> 1 -> 5.
Note: There can be leading zeros in the input lists, but there should not be any leading zeros in the output list.
Examples:
Input: num1 = 4 - > 5, num2 = 3 -> 4 -> 5
Output: 3 -> 9 -> 0Explanation: Given numbers are 45 and 345. There sum is 390.
Input: num1 = 0 -> 0 -> 6 -> 3, num2 = 0 -> 7
Output: 7 -> 0Explanation: Given numbers are 63 and 7. There sum is 70.
Constraints:
1 <= size of both linked lists <= 106
0 <= elements of both linked lists <= 9
Approach 01:
-
C++
-
Python
class Solution {
public:
Node* reverseLinkedList(Node* head) {
Node* previousNode = nullptr;
Node* currentNode = head;
while (currentNode) {
Node* nextNode = currentNode->next; // Save the next node
currentNode->next = previousNode; // Reverse the link
previousNode = currentNode; // Move previousNode to the current node
currentNode = nextNode; // Move to the next node
}
return previousNode;
}
Node* addTwoLists(Node* list1, Node* list2) {
// Reverse both linked lists
list1 = reverseLinkedList(list1);
list2 = reverseLinkedList(list2);
// Initialize result linked list and carry
Node* resultHead = nullptr;
int carryOver = 0;
while (list1 || list2 || carryOver) {
// Get values from the nodes or 0 if nullptr
int value1 = list1 ? list1->data : 0;
int value2 = list2 ? list2->data : 0;
// Compute the sum and carry
int totalSum = value1 + value2 + carryOver;
carryOver = totalSum / 10;
Node* newNode = new Node(totalSum % 10);
// Insert at the head of the result list
newNode->next = resultHead;
resultHead = newNode;
// Move to the next nodes in the input lists
if (list1) list1 = list1->next;
if (list2) list2 = list2->next;
}
// Remove leading zeros, if any
while (resultHead && resultHead->data == 0 && resultHead->next) {
resultHead = resultHead->next;
}
return resultHead;
}
};
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Solution:
def reverseLinkedList(self, head):
previousNode = None
currentNode = head
while currentNode:
nextNode = currentNode.next # Save the next node
currentNode.next = previousNode # Reverse the link
previousNode = currentNode # Move previousNode to the current node
currentNode = nextNode # Move to the next node
return previousNode
def addTwoLists(self, list1, list2):
# Reverse both linked lists
list1 = self.reverseLinkedList(list1)
list2 = self.reverseLinkedList(list2)
# Initialize result linked list and carry
resultHead = None
carryOver = 0
while list1 or list2 or carryOver:
# Get values from the nodes or 0 if None
value1 = list1.data if list1 else 0
value2 = list2.data if list2 else 0
# Compute the sum and carry
totalSum = value1 + value2 + carryOver
carryOver = totalSum // 10
newNode = Node(totalSum % 10)
# Insert at the head of the result list
newNode.next = resultHead
resultHead = newNode
# Move to the next nodes in the input lists
if list1: list1 = list1.next
if list2: list2 = list2.next
# Remove leading zeros, if any
while resultHead and resultHead.data == 0 and resultHead.next:
resultHead = resultHead.next
return resultHead
Time Complexity:
- Reversing Linked Lists:
Reversing each of the two input linked lists takes \( O(m) \) and \( O(n) \), where \( m \) and \( n \) are the lengths of the two lists, respectively.
- Summing Lists:
Adding the two reversed lists involves iterating through both lists once, taking \( O(\max(m, n)) \).
- Overall Time Complexity:
The total time complexity is \( O(m + n) \).
Space Complexity:
- Reversed Lists:
Reversing the input lists is done in-place, requiring \( O(1) \) extra space.
- Result List:
A new linked list is created to store the result, which requires \( O(\max(m, n)) \) space.
- Overall Space Complexity:
The total space complexity is \( O(\max(m, n)) \).