2 Add Two Numbers
程序员文章站
2024-03-17 22:18:16
...
Add Two Numbers
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
int get_list_len(ListNode* l)
{
int len = 0;
ListNode* temp = l;
while(temp)
{
len++;
temp = temp->next;
}
return len;
}
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int l1_len = get_list_len(l1);
int l2_len = get_list_len(l2);
int short_len = (l1_len > l2_len) ? l2_len : l1_len;
ListNode* list_temp = (l1_len > l2_len) ? l1 : l2;
ListNode* list = list_temp;
while(short_len)
{
short_len --;
list_temp->val = l1->val + l2->val;
list_temp = list_temp->next;
l1 = l1->next;
l2 = l2->next;
}
list_temp = list;
while(list_temp)
{
//printf("%d\n", list_temp->val);
if(list_temp->val >= 10)
{
if(list_temp->next)
{
list_temp->next->val += list_temp->val / 10;
}
else
{
list_temp->next = new ListNode(list_temp->val / 10);
}
list_temp->val = list_temp->val % 10;
}
list_temp = list_temp->next;
}
return list;
}
};
void trimLeftTrailingSpaces(string &input) {
input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
return !isspace(ch);
}));
}
void trimRightTrailingSpaces(string &input) {
input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
return !isspace(ch);
}).base(), input.end());
}
vector<int> stringToIntegerVector(string input) {
vector<int> output;
trimLeftTrailingSpaces(input);
trimRightTrailingSpaces(input);
input = input.substr(1, input.length() - 2);
stringstream ss;
ss.str(input);
string item;
char delim = ',';
while (getline(ss, item, delim)) {
output.push_back(stoi(item));
}
return output;
}
ListNode* stringToListNode(string input) {
// Generate list from the input
vector<int> list = stringToIntegerVector(input);
// Now convert that list into linked list
ListNode* dummyRoot = new ListNode(0);
ListNode* ptr = dummyRoot;
for(int item : list) {
ptr->next = new ListNode(item);
ptr = ptr->next;
}
ptr = dummyRoot->next;
delete dummyRoot;
return ptr;
}
string listNodeToString(ListNode* node) {
if (node == nullptr) {
return "[]";
}
string result;
while (node) {
result += to_string(node->val) + ", ";
node = node->next;
}
return "[" + result.substr(0, result.length() - 2) + "]";
}
int main() {
string line;
while (getline(cin, line)) {
ListNode* l1 = stringToListNode(line);
getline(cin, line);
ListNode* l2 = stringToListNode(line);
ListNode* ret = Solution().addTwoNumbers(l1, l2);
string out = listNodeToString(ret);
cout << out << endl;
}
return 0;
}
输入:[2,4,3] [5,6,4]
输出:[7, 0, 8]