Add numbers represented by Linked Lists in Java
For calculating the sum of the two numbers that are represented by a linked list, and then store the result in a new linked list. A linked list's head node is the most important digit, and each node is represented by a single digit.
For instance combining two numbers:
Algorithm:
- Create two linked lists using the following algorithm to represent the first two numbers.
- Both connected lists in reverse.
- Starting with the heads of the two linked lists, add the values of the two nodes (each node is represented as a single digit).
- Forward the carry if the total of the values for the top two nodes is more than 10. Observe the fundamental addition rules.
There are given two connected lists. A number is represented by each linked list. The objective is to calculate the total of the numbers each linked list represents. The solution must be presented as a linked list. We are aware that adding numbers from right to left can be used to find the combination of two numbers. Therefore, it is necessary to reverse the linked lists that are provided. However, we won't actually be flipping the linked list. Recursion will be used to mimic the same process. We will perform the fundamental calculation that we learned in primary school. Creating a new linked list with the sum in it after calculating the total.
NumberSumLinkedList.java
public class NumberSumLinkedList
{
static LinkedListNode h1;
static LinkedListNode h2;
static class LinkedListNode
{
int v;
LinkedListNode nxt;
LinkedListNode(int a)
{
v = a;
nxt = null;
}
}
void addTwoLinkedLists(LinkedListNode p, LinkedListNode q)
{
LinkedListNode begin1 = new LinkedListNode(0);
begin1.nxt = p;
LinkedListNode begin2 = new LinkedListNode(0);
begin2.nxt = q;
addPrecedingZeros(begin1, begin2);
LinkedListNode res = new LinkedListNode(0);
if (addTwoNodes(begin1.nxt, begin2.nxt, res) == 1)
{
LinkedListNode nde = new LinkedListNode(1);
nde.nxt = res.nxt;
res.nxt = nde;
}
displayLinkedList(res.nxt);
}
private int addTwoNodes(LinkedListNode li1, LinkedListNode li2, LinkedListNode ans)
{
if (li1 == null)
{ return 0;
}
int n = li1.v + li2.v + addTwoNodes(li1.nxt, li2.nxt, ans);
LinkedListNode nde = new LinkedListNode(n % 10);
nde.nxt = ans.nxt;
ans.nxt = nde;
return n/ 10;
}
private void addPrecedingZeros(LinkedListNode a1, LinkedListNode a2)
{
LinkedListNode nxt1 = a1.nxt;
LinkedListNode nxt2 = a2.nxt;
while (nxt1 != null && nxt2 != null)
{
nxt1 = nxt1.nxt;
nxt2 = nxt2.nxt;
}
if (nxt1 == null && nxt2 != null)
{
while (nxt2 != null)
{
LinkedListNode nde = new LinkedListNode(0);
nde.nxt = a1.nxt;
a1.nxt = nde;
nxt2 = nxt2.nxt;
}
}
else if (nxt2 == null && nxt1 != null)
{
while (nxt1 != null)
{
LinkedListNode nde = new LinkedListNode(0);
nde.nxt = a2.nxt;
a2.nxt = nde;
nxt1 = nxt1.nxt;
}
}
}
void displayLinkedList(LinkedListNode h)
{
while (h != null)
{
System.out.print(h.val + " ");
h = h.nxt;
}
System.out.println(" ");
}
public static void main(String[] argvs)
{
NumberSumLinkedList list = new NumberSumLinkedList();
list.h1 = new LinkedListNode(7);
list.h1.nxt = new LinkedListNode(9);
list.h1.nxt.nxt = new LinkedListNode(0);
list.h1.nxt.nxt.nxt = new LinkedListNode(5);
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(9);
list.h1.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(1);
list.h1.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(2);
System.out.print("The Initial List includes ");
list.displayLinkedList(h1);
list.h2 = new LinkedListNode(5);
list.h2.nxt = new LinkedListNode(3);
list.h2.nxt.nxt = new LinkedListNode(8);
list.h2.nxt.nxt.nxt = new LinkedListNode(4);
list.h2.nxt.nxt.nxt.nxt = new LinkedListNode(3);
list.h2.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(6);
list.h2.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(4);
System.out.print("The Second List includes ");
list.displayLinkedList(h2);
System.out.print("The Resultant List includes ");
list.addTwoLinkedLists(h1, h2);
System.out.println("\n");
list.h1 = new LinkedListNode(9);
list.h1.nxt = new LinkedListNode(8);
list.h1.nxt.nxt = new LinkedListNode(0);
list.h1.nxt.nxt.nxt = new LinkedListNode(4);
list.h1.nxt.nxt.nxt.nxt = new LinkedListNode(3);
list.h1.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(6);
list.h1.nxt.nxt.nxt.nxt.nxt.nxt = new LinkedListNode(2);
System.out.print("The Initial List includes ");
list.displayLinkedList(h1);
list.h2 = new LinkedListNode(8);
list.h2.nxt = new LinkedListNode(5);
list.h2.nxt.nxt = new LinkedListNode(7);
System.out.print("The Second List includes ");
list.displayLinkedList(h2);
System.out.print("The Resultant List includes ");
list.addTwoLinkedLists(h1, h2);
}
}
Output:
The Initial List includes 7 9 0 5 9 1 2
The Second List includes 5 3 8 4 3 6 4
The Resultant List includes 1 3 2 9 0 2 7 6
The Initial List includes 9 8 0 4 3 6 2
The Second List includes 8 5 7
The Resultant List includes 9 8 0 5 2 1 9
Analysis of Complexity: We must traverse both lists in order to add. Its overall number of elements in the initial linked list is a, as well as the entire number of elements with in second linked list is b, hence the program's time complexity is O(a + b). The program's space complexity is however O(a + b), since we additionally really have to store the final linked list.
Using the Iteration
In this method, the components including both linked lists will be stored on a stack. The Last In First Out (LIFO) principle of a stack is known to us. As a result, the very last node will emerge first.
Let the name of the file is NumberSumLinkedListDemo1.java
// significant import assertion
import java.util.Stack;
public class NumberSumLinkedListDemo1
{
// h1 will reference the initial node of the primary linked list.
static TheLinkedListNode h1;
static TheLinkedListNode h2;
// class for building linked list nodes
static class TheLinkedListNode
{
int valu;
TheLinkedListNode next;
// TheLinkedListNode class constructor
TheLinkedListNode(int e)
{
valu = e;
next = null;
}
}
// The procedure displays and combines the value of each
// entry in the two linked lists, ll2 & ll2
void addTheTwoLinkedLists(TheLinkedListNode l2, TheLinkedListNode l2)
{
// The components of the initial linked list are stacked.
Stack<Integer> stck1 = new Stack<Integer>();
// the second linked list's elements are added to a stack.
Stack<Integer> stck2 = new Stack<Integer>();
// adding elements to the resulting linked list's stack
Stack<Integer> restStack = new Stack<Integer>();
// incorporating items from the initial linked list into the stack
while(l2 != null)
{
stck1.push(l2.valu);
l2 = l2.next;
}
// the second linked list's items are being added to the stack
while(l2 != null)
{
stck2.push(l2.valu);
l2 = l2.next;
}
// calculating the stck1 and stck2 stacks' sizes
int h1 = stck1.size();
int h2 = stck2.size();
int hold = 0;
// add the linked list items from ll2 and ll2.
while(h1 != 0 && h2 != 0)
{
int x = stck1.pop();
int y = stck2.pop();
int digin = (x + y + hold) % 10;
hold = (x + y + hold) / 10;
// adding items to the stack from the resulting linked list
restStack.push(digin);
h1 = h1 - 1;
h2 = h2 - 1;
}
// when the first linked list's size is greater than
// the size of a second linked list
while(h1 != 0)
{
int x = stck1.pop();
int digin = (x + hold) % 10;
hold = (x + hold) / 10;
restStack.push(digin);
h1 = h1 - 1;
}
// if the second linked list's size is
// greater than first linked list
while(h2 != 0)
{
int x = stck2.pop();
int digin = (x + hold) % 10;
hold = (x + hold) / 10;
restStack.push(digin);
h2 = h2 - 1;
System.out.print("vbin ");
}
// Whenever hold isn't really zero and
// both linked lists' elements have all been
// processed, hold should be
// moved into the result stack.
if(hold != 0)
{
restStack.push(hold);
}
// calculating the stack's size restStack
int restStackSize = restStack.size();
TheLinkedListNode rest = new TheLinkedListNode(0);
TheLinkedListNode tempo = rest;
// from the resultant stack, create
// a loop for the consequent linked list.
while(restStackSize != 0)
{
tempo.next = new TheLinkedListNode(restStack.pop());
restStackSize = restStackSize - 1;
tempo = tempo.next;
}
// presenting technique for the linked list
TheDisplayLinkedList(rest.next);
}
// a technique to print the linked list
void TheDisplayLinkedList(TheLinkedListNode k)
{
while (k != null)
{
System.out.print(k.valu + " ");
k = k.next;
}
System.out.println(" ");
}
// It is the main method
public static void main(String[] argvs)
{
// constructing a TheNumberSumLinkedList2 object
TheNumberSumLinkedList2 list = new TheNumberSumLinkedList2();
// making the initial list
list.h1 = new TheLinkedListNode(7);
list.h1.next = new TheLinkedListNode(9);
list.h1.next.next = new TheLinkedListNode(0);
list.h1.next.next.next = new TheLinkedListNode(5);
list.h1.next.next.next.next = new TheLinkedListNode(9);
list.h1.next.next.next.next.next = new TheLinkedListNode(1);
list.h1.next.next.next.next.next.next = new TheLinkedListNode(2);
System.out.print("The Initial List includes ");
list.TheDisplayLinkedList(h1);
// assembling the second list
list.h2 = new TheLinkedListNode(5);
list.h2.next = new TheLinkedListNode(3);
list.h2.next.next = new TheLinkedListNode(8);
list.h2.next.next.next = new TheLinkedListNode(4);
list.h2.next.next.next.next = new TheLinkedListNode(3);
list.h2.next.next.next.next.next = new TheLinkedListNode(6);
list.h2.next.next.next.next.next.next = new TheLinkedListNode(4);
System.out.print("The Second List includes ");
list.TheDisplayLinkedList(h2);
System.out.print("The Resultant List includes ");
// combining the two lists, then displaying the outcome
list.addTheTwoLinkedLists(h1, h2);
System.out.println("\n");
// making the initial list
list.h1 = new TheLinkedListNode(9);
list.h1.next = new TheLinkedListNode(8);
list.h1.next.next = new TheLinkedListNode(0);
list.h1.next.next.next = new TheLinkedListNode(4);
list.h1.next.next.next.next = new TheLinkedListNode(3);
list.h1.next.next.next.next.next = new TheLinkedListNode(6);
list.h1.next.next.next.next.next.next = new TheLinkedListNode(2);
System.out.print("The Initial List includes ");
list.TheDisplayLinkedList(h1);
// assembling the second list
list.h2 = new TheLinkedListNode(8);
list.h2.next = new TheLinkedListNode(5);
list.h2.next.next = new TheLinkedListNode(7);
System.out.print("The Second List includes ");
list.TheDisplayLinkedList(h2);
System.out.print("The Resultant List includes ");
// combining the two lists, then displaying the outcomelist.addTheTwoLinkedLists(h1, h2);
}
} Output:
The Initial List includes 7 9 0 5 9 1 2
The Second List includes 5 3 8 4 3 6 4
The Resultant List includes 1 3 2 9 0 2 7 6
The Initial List includes 9 8 0 4 3 6 2
The Second List includes 8 5 7
The Resultant List includes 9 8 0 5 2 1 9
Analysis of Complexity: The program's time and spatial complexity are both the same as those mentioned before.