AlgorithmsAndDataStructures/LinkedListAddition.java at master · biprade/AlgorithmsAndDataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

public class LinkedListAddition {
public static void main(String[] args){

	// 1st number is 135 : 5->3->1
	Digit d1=new Digit();
	d1.data=1;
	Digit d2=new Digit();
	d2.data=1;
	Digit d3=new Digit();
	d3.data=1;

	d1.next=d2;
	d2.next=d3;
	d3.next=null;

	//2nd number is 26 : 6->2
	Digit d4=new Digit();
	d4.data=6;
	Digit d5=new Digit();
	d5.data=2;

	d4.next=d5;
	d5.next=null;

	Digit num1=d1;
	Digit num2=d4;

	forwardAddition(num1, num2);
}
static Digit reverseAddition(Digit num1,Digit num2,int carry){
	//base case
	if(num1==null && num2==null)
		return null;
	int digit1,digit2;
	if (num1!=null)
		digit1=num1.data;
	else digit1=0;
	if(num2!=null)
		digit2=num2.data;
	else
		digit2=0;

	int sum=digit1+digit2+carry;
	int digit=sum%10;
	Digit d=new Digit();
	d.data=digit;
	if(sum >=10){

		d.next=reverseAddition((num1==null)?null:num1.next,(num2==null)?null:num2.next,1);
	}
	else
		d.next=reverseAddition((num1==null)?null:num1.next, (num2==null)?null:num2.next, 0);
	return d;

}

static void forwardAddition(Digit num1,Digit num2){
	int l1=0;
	Digit g1=num1;
	Digit g2=num2;
	while(g1!=null){
		l1++;
		g1=g1.next;
	}
	int l2=0;
	while(g2!=null){
		l2++;

		g2=g2.next;

	}

	Digit n1=null;Digit n2=null;
	if (l1<l2){
		n1=padZero(num1,l2-l1);
		n2=num2;
	}
	else if(l2<l1){
		n2=padZero(num2,l1-l2);
		n1=num1;
	}
	else{
		n1=num1;n2=num2;

	}

	Result result=doAddition(n1,n2);
	if (result.carry==1){
		Digit d=new Digit();
		d.data=1;
		d.next=result.out;
		result.out=d;
	}
	while(result.out!=null){
		System.out.print(result.out.data+"->");
		result.out=result.out.next;
	}

}

static Result doAddition(Digit num1,Digit num2){


	if(num1.next==null && num2.next==null){
		int sum=num1.data+num2.data;
		int d=sum%10;
		Digit dg=new Digit();
		dg.data=d;
		Result rs=new Result();
		rs.out=dg;
		if(sum>=10)
			rs.carry=1;
		else
			rs.carry=0;
		return rs;
	}
	Result res=doAddition(num1.next, num2.next);
	int s=num1.data+num2.data+res.carry;
	int dig=s%10;
	Digit digit=new Digit();
	digit.data=dig;
	if (s>10)
		res.carry=1;
	else
		res.carry=0;
	digit.next=res.out;
	res.out=digit;
	return res;
}
static Digit padZero(Digit num,int numberOfZeroes){
Digit d = null;

while(numberOfZeroes!=0){
	d=new Digit();
	d.data=0;
	d.next=num;
	num=d;
	numberOfZeroes--;
}

return num;
}
}
class Digit{
	int data;
	Digit next;
}
//Wrapper class
class Result{
	int carry;
	Digit out;
}