You have given two linked list, which can be of same length or different. You have to add these lists and return sum in new list.
E.g: lists are 1 -> 2 -> 3 -> 4 & 5 -> 6 -> 7 -> 8 Sum would be 6->9->1->2
Approach 1:
Simplest solution is to reverse the lists and add from last and reverse the result and original lists as well.
We can also generate the result in reverse order as well so that we need not to reverse the result but only reverse original lists.
Solution below implement this approach.
public class test {
public static void main(String args[]) {
SllNode head1 = new SllNode(1);
head1.next = new SllNode(2);
head1.next.next = new SllNode(3);
head1.next.next.next = new SllNode(4);
SllNode head2 = new SllNode(5);
head2.next = new SllNode(6);
head2.next.next = new SllNode(7);
head2.next.next.next = new SllNode(8);
head2.next.next.next.next = new SllNode(9);
SllNode newH = AddSLL(head1, head2);
DisplaySll(newH);
}
public static void DisplaySll(SllNode head){
while (head != null){
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
public static SllNode AddSLL(SllNode head1, SllNode head2){
if(head1 == null){
return head2;
}
if (head2 == null){
return head1;
}
head1 = ReverseList(head1);
head2 = ReverseList(head2);
SllNode tempHead1 = head1;
SllNode tempHead2 = head2;
SllNode headN = new SllNode(0);
int carry = 0;
while (head1 != null && head2 != null){
int sum = carry + head1.data + head2.data;
headN.data = sum %10;
carry = sum/10;
SllNode temp = new SllNode();
temp.next = headN;
headN = temp;
head1 = head1.next;
head2 = head2.next;
}
while (head1!= null){
int sum = carry + head1.data;
headN.data = sum %10;
carry = sum/10;
SllNode temp = new SllNode();
temp.next = headN;
headN = temp;
head1 = head1.next;
}
while (head2!= null){
int sum = carry + head2.data;
headN.data = sum %10;
carry = sum/10;
SllNode temp = new SllNode();
temp.next = headN;
headN = temp;
head2 = head2.next;
}
if(carry > 0){
headN.data = carry;
}
else {
SllNode temp = headN;
headN = headN.next;
temp = null;
}
//If required reverse original lists
head1 = ReverseList(tempHead1);
head2 = ReverseList(tempHead2);
return headN;
}
public static SllNode ReverseList(SllNode head){
SllNode prevNode = null;
while (head != null){
SllNode temp = head;
SllNode newHEad = head.next;
head.next = prevNode;
head = newHEad;
prevNode = temp;
}
return prevNode;
}
static class SllNode{
public int data;
public SllNode next;
public SllNode(){
next = null;
}
public SllNode(int val){
next = null;
this.data = val;
}
public SllNode(int val, SllNode nextNode){
next = nextNode;
data = val;
}
}
}
Approach 2:If we do not want to reverse the list, we can use recursive approach to find the sum.
Solution below implement this approach.
public class test {
public static void main(String args[]) {
SllNode head1 = new SllNode(1);
head1.next = new SllNode(1);
head1.next.next = new SllNode(1);
head1.next.next.next = new SllNode(1);
SllNode head2 = new SllNode(9);
head2.next = new SllNode(9);
head2.next.next = new SllNode(9);
head2.next.next.next = new SllNode(9);
head2.next.next.next.next = new SllNode(9);
DisplaySll(head1);
DisplaySll(head2);
SllNode newH = AddWithoutReverse(head1, head2);
System.out.println("with recursion : ");
DisplaySll(newH);
}
public static int FindLength(SllNode head){
int lenght = 0;
while (head != null){
head = head.next;
lenght++;
}
return lenght;
}
public static SllNode AddWithoutReverse(SllNode head1, SllNode head2){
if(head1 == null){
return head2;
}
if (head2 == null){
return head1;
}
int length1 = FindLength(head1);
int length2 = FindLength(head2);
SllNode tempHead = head1;
SllNode tempHead2 = head2;
if(length1 != length2){
int l1 = length1;
int l2 = length2;
if(l1 > l2){
while (l1 > l2){
tempHead = tempHead.next;
l1--;
}
}
else {
while (l2 > l1){
tempHead2 = tempHead2.next;
l2--;
}
}
}
SllNode listSum = SllAdd(tempHead, tempHead2);
int carry = 0;
if (listSum.data /10 > 0){
carry = listSum.data/10;
listSum.data = listSum.data%10;
}
SllNode remaining = null;
if(length1 != length2) {
if(length1 > length2){
remaining = AddSingle(head1, carry, length1, length2);
}
else {
remaining = AddSingle(head2, carry, length2, length1);
}
}
SllNode rHead = remaining;
while (remaining.next != null){
remaining = remaining.next;
}
remaining.next = listSum;
if (rHead.data /10 > 0){
carry = rHead.data/10;
rHead.data = rHead.data%10;
SllNode temp = new SllNode(carry, rHead);
rHead = temp;
}
return rHead;
}
private static SllNode AddSingle(SllNode head, int carry, int length1, int length2){
if(length1-1 > length2){
SllNode temp = new SllNode();
temp.next = AddSingle(head.next, carry, length1-1, length2);
temp.data = temp.next.data/10 + head.data;
temp.next.data = temp.next.data % 10;
return temp;
}
SllNode newNode = new SllNode();
newNode.data = carry + head.data;
return newNode;
}
private static SllNode SllAdd(SllNode h1, SllNode h2){
if(h1 != null && h2 != null){
SllNode sumNode = new SllNode();
sumNode.next = SllAdd(h1.next, h2.next);
int carry = 0;
if(sumNode.next != null){
carry = sumNode.next.data / 10;
sumNode.next.data = sumNode.next.data % 10;
}
sumNode.data = h1.data + h2.data + carry;
return sumNode;
}
return null;
}
public static void DisplaySll(SllNode head){
while (head != null){
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
static class SllNode{
public int data;
public SllNode next;
public SllNode(){
next = null;
}
public SllNode(int val){
next = null;
this.data = val;
}
public SllNode(int val, SllNode nextNode){
next = nextNode;
data = val;
}
}
}
Comments are welcome.
No comments:
Post a Comment