Hey Guys, a warm welcome to tech-maze, in todays article we will see a program and its implementation which is frequently asked in FAANG companies.
The question is to calculate sum of two linked list and sum should display in the form of another linked list.
This question can be asked in following two ways
1st way :
Two list will be given, where first list is 3->2->1, representing the number 123 and second list 4->5->6 representing the number 654 because in mathematics we start summing two numbers from right to left but in singly linked list we traverse from left to right unless we reverse it.
2nd way :
Two list will be given, where first list is 3->2->1, representing the number 321 and second list 4->5->6 representing the number 456, in this case we have to reverse the list and then perform the addition.
Lets proceed with 1st way and see the code with explanation
public Node addTwoLinkedList(Node node1, Node node2) {
Node temp = new Node(0);
Node node3 = temp;
int carry = 0;
while(node1!=null || node2!=null) {
int val1 = node1!=null ? node1.getVal() : 0;
int val2 = node2!=null ? node2.getVal() : 0;
int sum = val1 + val2 + carry;
carry = sum/10;
int digit = sum%10;
Node tmp = new Node(digit);
node3.setNext(tmp);
node3 = node3.getNext();
if(node1!=null)
node1 = node1.getNext();
if(node2!=null)
node2 = node2.getNext();
}
if(carry>0) {
Node tmp = new Node(carry);
node3.setNext(tmp);
}
return temp;
}
above method takes two linked list as input parameter, the logic is quite simple but we have to take care of many negative scenarios, otherwise code will throw exception
Logic proceeds in following steps ::
Step 1 :-
null check for both the list with OR operator as both list might not be of same size.
for example : first list may represents a number 345 and second list may represents 5462, both are of different size, hence to find the sum we have to enter the loop, that's the reason we have used OR operator.
Step 2 :-
get the value from list, if list is null then value should be 0, this condition fulfill the scenario where size of both the list is not equal
Step 3 :-
here, we have to take care, that case as well where sum of two digit exceed 9, in this case we have to carry forward the number and do add to next sum of digits.
Step 4 :-
get the number by using modulus and create a temp node, later add this in the third list which contains the result on completion of while loop.
move pointer to next node for first list, second list and third list.
Step 5 :-
when this process finishes, we have to check the carry variable again and if it is more than 0 then create a node and attach that to third list and return the temp list which points the first node of third list.
here process of adding two linked list finishes and now we have third list which contains the result.
Now lets check the 2nd way ------
public Node addTwoLinkedListAfterReversing(Node node1, Node node2) {
Node temp = new Node(0);
Node node3 = temp;
int carry = 0;
node1 = reverseLinkedList(node1);
node2 = reverseLinkedList(node2);
while(node1!=null || node2!=null) {
int val1 = node1!=null ? node1.getVal() : 0;
int val2 = node2!=null ? node2.getVal() : 0;
int sum = val1 + val2 + carry;
carry = sum/10;
int digit = sum%10;
Node tmp = new Node(digit);
node3.setNext(tmp);
node3 = node3.getNext();
if(node1!=null)
node1 = node1.getNext();
if(node2!=null)
node2 = node2.getNext();
}
if(carry>0) {
Node tmp = new Node(carry);
node3.setNext(tmp);
}
return temp;
}
public Node reverseLinkedList(Node head) {
if(head == null)
return null;
Node cur = head;
Node next = null;
Node prev = null;
while(cur!=null) {
next = cur.getNext();
cur.setNext(prev);
prev = cur;
cur = next;
}
head = prev;
return head;
}
above method takes two linked list as input parameter, the logic will be same as the previous one except one step, here we have to reverse the list first and then proceed with the usual steps which has explained in 1st way.
Please find details below to understand how a list can be reversed
In many programming interviews or while working on project, to achieve a particular scenario we have to reverse the list and then proceed with the implementation.
following code reverse the list, lets see how it does :
public Node reverseLinkedList(Node head) {
if(head == null)
return null;
Node cur = head;
Node next = null;
Node prev = null;
while(cur!=null) {
next = cur.getNext();
cur.setNext(prev);
prev = cur;
cur = next;
}
head = prev;
return head;
}
here we pass the head node of the list as input parameter, now the logic proceed as below
Step 1 :- check the negative scenario
Step 2 :- take three nodes and name them as prev, next and cur, cur points to head node
Step 3 :- now run a loop and start connecting the nodes in reverse direction,
so if list is 3->5->2->6->7->null
on finishing first iteration list will change to 3<-5->2->6->7->null
and prev will become cur and cur will become next
on finishing second iteration list will change to 3<-5<-2->6->7->null
same process will repeat until pointer reach to last node and we get the reversed list which is
null<-3<-5<-2<-6<-7
or
7->6->->2->5->3->null
now point head to prev, in this case head will point to 7
process of reversing the list has completed.
That's all folks, hope this will help at some extent, for more details and complete code please have a look in the below GitHub project, I will come up with another article shortly.
Git location for the demo : https://github.com/rohitmodi07/Programs
A Big thank you for checking out my article, this really encourage me to come up with more topics.
Comments