Introduction
Welcome to Art of Coding’s blog. Today, we’ll discuss a challenge that stands out as one of the most frequently requested in programming interviews, as listed on LeetCode: Add Two Numbers.
In this article, we’ll detail the problem of adding numbers using Linked Lists, followed by solutions implemented in Java and Python. Additionally, we’ll conduct a thorough analysis of the time and space complexity of the algorithm.
Problem Explanation
In this challenge, we tackle the task of adding two numbers represented by two separate linked lists. Each node in these lists holds a single digit, arranged in reverse order. This unique setup mirrors the manual addition process, starting from the least significant digits (the units) and advancing towards the most significant, while managing any carry-over along the way.
Let’s take a practical example:
Imagine we’re working with two numbers: 759 and 246. Within the linked lists, the number 759 is represented as 9 -> 5 -> 7, while 246 is denoted as 6 -> 4 -> 2. Adding these numbers together yields 1005, which translates to a linked list formation of 5 -> 0 -> 0 -> 1 in the reversed order.
This example clearly shows the process of dealing with each digit independently and the progression of the carry-over during the sum.
The challenge is a robust test of skills in handling linked lists and grasping the essentials of numerical operations.
Java and Python Implementation
Let’s now explore a solution in both Java and Python for the problem of adding two numbers represented by linked lists (Add Two Numbers). This code accounts for the reversal of digits and the propagation of the carry-over, creating a new linked list that represents the sum of the numbers.
class SumNumbers {
public static NodeList addTwoNumbers(NodeList list1, NodeList list2) {
NodeList head = new NodeList(0);
NodeList currentNode = head;
int carryOver = 0;
while (list1 != null || list2 != null || carryOver > 0) {
int n1 = list1 == null ? 0 : list1.value;
int n2 = list2 == null ? 0 : list2.value;
int sum = n1 + n2 + carryOver;
carryOver = sum / 10;
currentNode.next = new NodeList(sum % 10);
currentNode = currentNode.next;
list1 = list1 != null ? list1.next : null;
list2 = list2 != null ? list2.next : null;
}
return head.next;
}
}
class NodeList {
int value;
NodeList next;
NodeList(int value) {
this.value = value;
}
}
class Node:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def add_two_numbers(list1, list2):
head = Node(0)
current = head
carry_over = 0
while list1 or list2 or carry_over:
n1 = list1.value if list1 else 0
n2 = list2.value if list2 else 0
total = n1 + n2 + carry_over
carry_over = total // 10
current.next = Node(total % 10)
current = current.next
list1 = list1.next if list1 else None
list2 = list2.next if list2 else None
return head.next
node1 = Node(9)
node1.next = Node(5)
node1.next.next = Node(7)
node2 = Node(6)
node2.next = Node(4)
node2.next.next = Node(2)
# Adding the two numbers
result = add_two_numbers(node1, node2)
# Printing the result
while result:
print(result.value, end=" -> ")
result = result.next
Code Explanation
- The
addTwoNumbersmethod initially creates a dummy node (head) pointing to the first element of the list, which simplifies manipulation and eliminates the need for special checks on the first node.
Code Explanation
- The
addTwoNumbersmethod initially creates a (head) pointing to the first element of the list, which simplifies manipulation and eliminates the need for special checks on the first node. - Within the
whileloop, we check whether there are any nodes left to process in either list or if there’s a remaining carry-over. - We calculate the sum of the current values (
n1andn2) from each list, along with any previous carry-over. - he carry-over for the next iteration is determined by dividing the current sum by 10 (
carryOver = sum / 10). - A new node with the least significant digit of the sum (
sum % 10) is created and appended to the resulting list. - We progress through the input lists by moving
list1andlist2to their respective next nodes. - After the loop concludes, if there’s still a carry-over, we add a new node to the end of the resulting list.
- The sum’s result is the linked list starting from the node following the temporary dummy head, as this was merely an initial marker to avoid special checks.”
Handling Lists of Different Lengths
The implementation efficiently manages lists of varying lengths. If one list is longer than the other, the algorithm continues to process the remaining nodes, ensuring that each digit is accounted for and that no carry-over is lost.
For instance: the first list represents the number 513 (stored as 3 -> 1 -> 5), and the second list represents the number 29 (stored as 9 -> 2). The longer list has an additional digit to be processed after the shorter list has been fully traversed.
Complexity Analysis
Time Complexity Analysis
In our code, the main loop runs once for each element in both linked lists. Thus, if ‘N’ represents the number of elements in the longer list, our algorithm has a time complexity of O(n). This means that the time required to complete the addition is proportional to the size of the longer list.
Space Complexity Analysis
The memory usage in our algorithm is primarily due to the new linked list that represents the resultant sum. Therefore, the space complexity is also O(n), as in the worst-case scenario, a carry-over could result in an additional node. Hence, for lists of size ‘n’, we need space for ‘n + 1’ nodes.
In summary, our algorithm exhibits linear complexity in both time and space dimensions.
Conclusion
In conclusion, we’ve navigated the nuances of adding numbers via linked lists—a task that tests both our logic and our understanding of fundamental data structures. The Java and Python implementations we’ve discussed serve as a solid foundation for tackling similar problems and refining coding proficiency.
Are you ready to dive even deeper? If you found this guide helpful, be sure to check out our previous article on ‘Detecting Cycles in Linked Lists.‘ It’s a perfect next step to expand your knowledge
Engage with us, share your thoughts, and stay tuned for more insights!
Pingback: Preparação para Entrevistas: #13 - Somando números em Listas Encadeadas - A Arte de Programar