Introduction: Adding two numbers is a fundamental operation in mathematics. However, when the numbers are given as linked lists, the problem becomes more complicated. In this blog post, we will explore how to add two numbers given as linked lists.
What is a linked list? A linked list is a data structure that consists of a sequence of nodes. Each node contains a value and a pointer to the next node in the sequence. Linked lists are commonly used to implement dynamic data structures, such as stacks, queues, and associative arrays.
Addition of Two Numbers Given as Linked Lists: Let’s say we have two numbers represented as linked lists, num1 and num2. We can add them as follows:
- Initialize two pointers, p1 and p2, to the heads of num1 and num2, respectively.
- Initialize a carry variable, carry, to 0.
- Initialize a new linked list, result, to store the sum of num1 and num2.
- Traverse both linked lists simultaneously until both pointers reach the end of the lists.
- At each iteration, add the values of p1 and p2, as well as the carry from the previous iteration. If the sum is greater than 9, set the carry to 1, and subtract 10 from the sum. Otherwise, set the carry to 0.
- Add the result of the sum to a new node in the result linked list.
- Move both pointers to the next nodes in their respective lists.
- If one list is longer than the other, continue adding the remaining digits of the longer list to the result list, with the carry, if any.
- Return the head of the result linked list.
Example: Let’s take an example to understand this better. Suppose we have two numbers, num1 = 243 and num2 = 465, represented as linked lists:
num1: 2 -> 4 -> 3 -> NULL num2: 4 -> 6 -> 5 -> NULL
To add these two numbers, we will follow the above steps:
- Initialize p1 to the head of num1 (2) and p2 to the head of num2 (4).
- Initialize carry to 0.
- Initialize an empty linked list, result.
- Traverse both linked lists simultaneously until both pointers reach the end of the lists.
- At the first iteration, add 2 and 4, as well as the carry (0), to get 6. Add 6 to the result linked list.
- Move both pointers to the next nodes in their respective lists.
- At the second iteration, add 4 and 6, as well as the carry (0), to get 10. Set the carry to 1 and subtract 10 from the sum to get 0. Add 0 to the result linked list.
- Move both pointers to the next nodes in their respective lists.
- At the third iteration, add 3 and 5, as well as the carry (1), to get 9. Add 9 to the result linked list.
- Since both pointers have reached the end of their respective lists, we are done.
- Return the head of the result linked list (6 -> 0 -> 9 -> NULL).
Conclusion: In this blog post, we learned how to add two numbers given as linked lists. We followed a simple algorithm that involves traversing both linked lists simultaneously and adding the corresponding digits at each iteration. We also saw an example to understand this better. With this knowledge, you can now easily solve problems that involve adding two numbers given as
Sure, I can help you create a Java program for adding two numbers given as linked lists. Here’s the code:
javaCopy code/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1;
ListNode p2 = l2;
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;
while (p1 != null || p2 != null) {
int sum = carry;
if (p1 != null) {
sum += p1.val;
p1 = p1.next;
}
if (p2 != null) {
sum += p2.val;
p2 = p2.next;
}
carry = sum / 10;
sum %= 10;
current.next = new ListNode(sum);
current = current.next;
}
if (carry != 0) {
current.next = new ListNode(carry);
}
return dummy.next;
}
}
Explanation: The addTwoNumbers() method takes two linked lists l1 and l2 as input and returns the sum of the two linked lists as a new linked list.
We first initialize two pointers p1 and p2 to the heads of l1 and l2, respectively. We also initialize a dummy node and a current node to keep track of the result. We also initialize a carry variable to 0.
We then traverse both linked lists simultaneously using a while loop until both pointers reach the end of their respective lists. At each iteration, we add the values of p1 and p2, as well as the carry from the previous iteration. If the sum is greater than 9, we set the carry to 1 and subtract 10 from the sum. Otherwise, we set the carry to 0. We then add the result of the sum to a new node in the result linked list.
We then move both pointers to the next nodes in their respective lists. If one list is longer than the other, we continue adding the remaining digits of the longer list to the result list, with the carry, if any.
Finally, if there is a carry after adding the last digits of both lists, we add a new node with the carry to the result list.
We return the head of the result linked list, which is the second node in the dummy node.
