Repository navigation
Expand file tree
/
Copy pathQ25-AddLinkedList.cpp
More file actions
100 lines (84 loc) · 2.87 KB
/
Copy pathQ25-AddLinkedList.cpp
File metadata and controls
100 lines (84 loc) · 2.87 KB
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
//
// Q25-AddLinkedList.cpp
// Algorithm-Linux
//
// Created by Sanqiang Zhao on 12/6/12.
// Copyright (c) 2012 Sanqiang Zhao. All rights reserved.
//
/*
LinkedListElement<int> *l1 = new LinkedListElement<int>(9);
LinkedListElement<int> *l2 = new LinkedListElement<int>(2);
LinkedListElement<int> *l3 = new LinkedListElement<int>(4);
LinkedListElement<int> *l4 = new LinkedListElement<int>(1);
LinkedListElement<int> *l5 = new LinkedListElement<int>(5);
LinkedListElement<int> *l6 = new LinkedListElement<int>(9);
l1->setNext(l2); l2->setNext(l3);
l4->setNext(l5); l5->setNext(l6);
l1->print(); l4->print();
//LinkedListElement<int> *result = addLinkedListAsc(l1, l4, 0);
//result->print();
LinkedListElement<int> *result = addLinkedListDesc(l1, l4);
result->print();
*/
#include "Q25-AddLinkedList.h"
LinkedListElement<int> * addLinkedListAsc(LinkedListElement<int> *left, LinkedListElement<int> *right,int carry)
{
int sum = carry;
if (left) {
sum += left->Data;
}
if (right) {
sum +=right->Data;
}
int digit = sum % 10;
int next_carry = sum / 10;
LinkedListElement<int> *node = new LinkedListElement<int>(digit);
if (next_carry != 0 || left || right) {
node->setNext(addLinkedListAsc(left->Next, right->Next,next_carry));
}
return node;
}
LinkedListElement<int> * addLinkedListDesc(LinkedListElement<int> *left, LinkedListElement<int> *right)
{
int length_left= left->getLength();
int length_right = right->getLength();
if (length_left>length_right) {
padList(right, length_left-length_right);
}else if(length_left<length_right)
{
padList(left, length_right-length_left);
}
addLinkedListDescHelperWrapper* wrapper = addLinkedListDescHelper(left, right);
if (wrapper->carry != 0) {
LinkedListElement<int> *head = new LinkedListElement<int>(wrapper->carry);
head->Next = wrapper->node;
return head;
}else{
return wrapper->node;
}
}
addLinkedListDescHelperWrapper* addLinkedListDescHelper(LinkedListElement<int> *left,LinkedListElement<int> *right)
{
if (!left && !right) {
addLinkedListDescHelperWrapper *empty = new addLinkedListDescHelperWrapper();
return empty;
}
addLinkedListDescHelperWrapper *wrapper = addLinkedListDescHelper(left->Next, right->Next);
int sum = left->Data + right->Data + wrapper->carry;
int digit = sum % 10;
int next_carry = sum / 10;
LinkedListElement<int> * node = new LinkedListElement<int>(digit);
node->Next = wrapper->node;
wrapper->carry = next_carry;
wrapper->node = node;
return wrapper;
}
void padList(LinkedListElement<int> *&node, int length)
{
int i=0;
for (; i<length; ++i) {
LinkedListElement<int> *temp = new LinkedListElement<int>(0);
temp->Next=node;
node=temp;
}
}