欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]