See the following running example that adds two numbers which is represented by linked list.
Steps adding two numbers represented by linked list:-
1. Reverse both linked lists
2. Now add both linked list data from starts to end.
3. New linked list get which is in reverse order of actual addition of both linked list
4. Reverse the added linked list and get your result.
package com.ds.linkedlist;
public class AddTwoNumbersOfLinkedList {
Node head;
public static void main(String[] args) {
AddTwoNumbersOfLinkedList l1 = new AddTwoNumbersOfLinkedList();
l1.insert(1);
l1.insert(2);
l1.insert(3);
l1.insert(4);
l1.insert(5);
l1.insert(9);
AddTwoNumbersOfLinkedList l2 = new AddTwoNumbersOfLinkedList();
l2.insert(9);
l2.insert(6);
l2.insert(3);
System.out.println("List1: ");
l1.print();
System.out.println("\nList2: ");
l2.print();
AddTwoNumbersOfLinkedList addTwoList = new AddTwoNumbersOfLinkedList();
Node addedList = addTwoList.addNumbersOfLinkedList(l1.head, l2.head);
}
private Node addNumbersOfLinkedList(Node list1, Node list2) {
list1 = reverseList(list1);
list2 = reverseList(list2);
System.out.println("\nAfter Reverse List1: ");
this.head = list1;
print();
System.out.println("\nAfter Reverse List2: ");
this.head = list2;
print();
Node added = addLinkedList(list1, list2);
this.head = added;
System.out.println("\nAdded Reverse List: ");
print();
this.head = reverseList(added);
System.out.println("\nAdded List: ");
print();
return added;
}
private Node addLinkedList(Node list1, Node list2) {
this.head = null;
if(list1 == null && list2 == null)
return null;
else if(list1 == null)
return list2;
else if(list2 == null)
return list1;
int sum = 0, carry = 0, reminder = 0;
//Both having same number of nodes
while(list1 != null && list2 != null){
sum = carry + list1.data + list2.data;
carry = sum/10;
if(carry == 0){
insert(sum);
reminder = 0;
}else{
reminder = sum%10;
insert(reminder);
}
list1 = list1.next;
list2 = list2.next;
}
//If list1 is bigger
while(list1 != null){
if(carry == 0){
insert(list1.data);
}else{
sum = carry + list1.data;
carry = sum/10;
if(carry == 0){
insert(sum);
reminder = 0;
}else{
reminder = sum%10;
insert(reminder);
}
}
list1 = list1.next;
}
//If list2 is bigger
while(list2 != null){
if(carry == 0){
insert(list2.data);
}else{
sum = carry + list2.data;
carry = sum/10;
if(carry == 0){
insert(sum);
reminder = 0;
}else{
reminder = sum%10;
insert(reminder);
}
}
list2 = list2.next;
}
if(carry > 0){
insert(carry);
}
return this.head;
}
private Node reverseList(Node list) {
Node prev = null;
while(list.next != null){
Node next = list.next;
list.next = prev;
prev = list;
list = next;
}
list.next = prev;
return list;
}
private class Node{
int data;
Node next;
Node(int data){
this.data = data;
}
}
public void insert(int data){
Node newNode = new Node(data);
if(head == null){
head = newNode;
}else{
Node curr = head;
while(curr.next != null){
curr = curr.next;
}
curr.next = newNode;
}
}
public void print(){
if(head==null)
return;
Node curr = head;
while(curr != null){
System.out.print(curr.data + " ");
curr = curr.next;
}
}
}
Output:-
List1:
1 2 3 4 5 9
List2:
9 6 3
After Reverse List1:
9 5 4 3 2 1
After Reverse List2:
3 6 9
Added Reverse List:
2 2 4 4 2 1
Added List:
1 2 4 4 2 2