Суммирования чисел, представленных в виде связанных списков


Описание Проблемы:

Вам даны две непустые связные списки представляют два неотрицательных целые числа. Цифры хранятся в обратном порядке, и каждый из их узлы содержат одну цифру. Добавить два числа и вернуть его как связанный список.

Можно предполагать, что два числа не содержат нуль, кроме сам номер 0.

Пример:

Вход: (2,4,3) + (5,6,4)

Выход: 7,0,8

Объяснение: 342 + 465 = 807

Я сделал проблему кодирования и мне интересно, что я мог бы сделать лучше или сделать по-другому.

 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *l3 = new ListNode(0);

    if(l1->next!=NULL && l2->next!=NULL)
    {
       l3->next = addTwoNumbers(l1->next,l2->next);

        if(l3->next->val>9)
        {
             ListNode *temp;
             temp = l3;
           while(temp->next->val>9)
          {
              temp->next->next->val+=1;
             temp->next->val-=10;
             l3->val = l1->val+l2->val;
            temp = temp->next;
          }
            return l3;
        }

        else{
             l3->val = l1->val + l2->val;

             if(l3->val>9)
            {
                ListNode *tempB;
                tempB = l3;
                while(tempB->val>9)
                {
                     if(tempB->next != NULL)
                    {
                     tempB->next->val+=1;
                      tempB->val-=10;
                      tempB = tempB->next;
                     }
                    else{    

                     ListNode *H = new ListNode(1);
                     tempB->next = H;
                     tempB->val -= 10;
                     tempB = tempB->next;

                    }
                }
                return l3;
             }


             return l3;
            }

        }

    else if(l1->next ==  NULL && l2->next != NULL)
    {
        ListNode *temp = new ListNode(0);
        l3->next = addTwoNumbers(temp,l2->next);
         l3->val = l1->val + l2->val;
            if(l3->val>9)
            {
                ListNode *tempB;
                tempB = l3;
                 while(tempB->val>9)
                {
                     if(tempB->next != NULL)
                    {
                     tempB->next->val+=1;
                      tempB->val-=10;
                      tempB = tempB->next;
                     }
                    else{    

                     ListNode *H = new ListNode(1);
                     tempB->next = H;
                     tempB->val -= 10;
                     tempB = tempB->next;

                    }
                }
                return l3;
            }
        else 
            return l3;
    }

    else if(l2->next ==  NULL && l1->next != NULL)
    {
        ListNode *temp = new ListNode(0);
        l3->next = addTwoNumbers(l1->next,temp);
         l3->val = l1->val + l2->val;
            if(l3->val>9)
            {
                ListNode *tempB;
                tempB = l3;
                 while(tempB->val>9)
                {
                     if(tempB->next != NULL)
                    {
                     tempB->next->val+=1;
                      tempB->val-=10;
                      tempB = tempB->next;
                     }
                    else{    

                     ListNode *H = new ListNode(1);
                     tempB->next = H;
                     tempB->val -= 10;
                     tempB = tempB->next;

                    }
                }
                return l3;
            }
        else 
            return l3;
    }

    else{
        l3->val = l1->val + l2->val;
        if(l3->val>9)
        {
            ListNode* l4 = new ListNode(1);
            l3->val -=10;
            l3->next = l4;
            return l3;
        }
        else{
            return l3;
        }

    }
}


Комментарии
3 ответа

Ну, ваш код обрабатывает все, в особом случае. Что не только не хватает элегантности, это очень многословный, подверженных ошибкам и неэффективным.


  1. Во-первых, проблема симметрично в два аргумента. Таким образом, вы можете поменять аргументы ничего не меняя.

  2. Вы не только чтения прошли списки, никогда не изменяя их. Так, const представляется целесообразным.

  3. Если распределение бросков, вы просто утечка всех уже выделенных узлов. Это вообще inacceptible.

  4. Рекомендуется написать список класса, вместо того, чтобы бросать вокруг свободные узлы.

  5. Вашу проблему лучше решать с помощью итераций, чем рекурсия, как C++ не ГК и не гарантирует хвост-рекурсия.

Итак, давайте посмотрим на это снова, но использовать итерации. Все равно, я не буду писать список-абстракция, так что бы большую часть сама по себе:

 ListNode* addTwoNumbers(const ListNode* a, const ListNode* b) {
ListNode dummy(0);
auto p = &dummy;
int carry = 0;

try {
while (a && b) {
carry += a->val + b->val;
p = p->next = new ListNode(carry % 10);
carry /= 10;
a = a->next;
b = b->next;
}

if(b)
a = b;
while (a) {
carry += a->val;
p = p->next = new ListNode(carry % 10);
carry /= 10;
a = a->next;
}

if (carry)
p->next = new ListNode(carry);

return dummy->next;
}
catch (...) {
p = dummy->next;
while (p) {
auto x = p->next;
delete p;
p = x;
}
throw;
}
}

10
ответ дан 25 марта 2018 в 08:03 Источник Поделиться

Первый: разбить его на несколько методов.

Во-вторых: вы можете resuse части вашего кода: f(l1->next == NULL && l2->next != NULL) и if(l2->next == NULL && l1->next != NULL) будут одинаковыми, если l1и l2 являются взаимозаменяемыми.

Зачем нужно инициализировать ListNode С 0 или 1 и потом переназначить значение с суммой цифр? Это может быть сделано сразу.

Когда только один список все еще содержит цифр обработка может быть упрощена путем специализации.

Лично я не люблю переменные, такие как l1, l2, l3 особенно как l и 1 может быть трудно отличить.

Выше я пытался реструктуризировать ваш код (без проверки на ошибки, внесенные меня), чтобы уточнить мои предложения.

struct ListNode {
ListNode* next;
int val;

ListNode(int arg) { next = nullptr; val = arg; }
};

ListNode* addTwoNumbers(ListNode* node1, ListNode* node2)
{
if (node1->next != nullptr && node2->next != nullptr)
{
return addTwoNodes(node1, node2);
}

else if (node1->next == nullptr && node2->next != nullptr)
{
return addOneNode(node1->val, node2);
}

else if (node2->next == nullptr && node1->next != nullptr)
{
return addOneNode(node2->val, node1);
}

else {
return addTwoDigits(node1->val, node2->val);
}
}

ListNode* addTwoNodes(ListNode* node1, ListNode* node2)
{
ListNode *result = new ListNode(node1->val + node2->val);
if (result->val > 9)
{
result->val -= 10;
ListNode tmp(1);
if (node1->next != nullptr)
{
ListNode const * const next = node1->next;
tmp.val += next->val;
tmp.next = next->next;
}
result->next = addTwoNumbers(&tmp, node2->next);
}
else
{
result->next = addTwoNumbers(node1->next, node2->next);
}
return result;
}

ListNode* addOneNode(int val, ListNode* node)
{
ListNode *result = new ListNode(val + node->val);
if (result->val > 9)
{
result->val -= 10;
result->next = addOneNode(1, node->next);
}
else
{
ListNode *tmp = result;
for (ListNode *arg = node->next; arg != nullptr; arg = arg->next)
{
result->next = new ListNode(arg->val);
}
}
return result;
}

ListNode* addTwoDigits(int val1, int val2)
{
ListNode *result = new ListNode(val1 + val2);

if (result->val > 9)
{
result->val -= 10;
result->next = new ListNode(1);
}
return result;
}

4
ответ дан 25 марта 2018 в 07:03 Источник Поделиться

Я предлагаю вам написать логику на простом английском языке, прежде чем включать его в код.


To add two lists:
* Add the first digits
* If the sum is less than ten:
* Store the sum
* Add the rest of the lists
else
* Subtract ten
* Store the sum (after subtraction)
* Add the rest of the lists with the carried ten
Keep going until you've run out digits in both lists.

При наличии письменного плана перед вами, вы найдете его легче, чтобы четко структурировать свой код и держать его коротким.

Подумайте о "контракте" функции: что именно нужно на выходе addTwoNumbers выглядеть? В коде строку if(l3->next->val>9) красный флаг: это не должно быть возможным, чтобы хранить числа больше 9 в узел!

Теперь пару подлые трюки, чтобы сделать его проще:

Помню те логическим классам схемотехника откуда вы узнали про бинарный "половина гадюка", а затем "полный сумматор"? Так что у вас есть "добавить" и "добавить с функции". Но c++ позволяет аргументов по умолчанию, так что вы можете свернуть их в одну функцию (если носить не указан, он равен нулю).

Вместо того, "если это-нуль" проверяется в нескольких местах в вашей функции, вы можете положить, что логика в вспомогательную функцию, и его лечить нули как нули.

(Примечание: Я не использую c++ профессионально ... я пишу больше с точки зрения дизайна алгоритм, а не особенности языка, а Deduplicator предупреждает нас в комментариях, что указатели-это сложно!--если вы хотите использовать это в производственной системе, есть немного больше работы, чтобы быть сделано.)

Собираем все вместе, я получаю эту версию:

#include <iostream>
using namespace std;

struct Digits {
Digits* next_node;
int value;

Digits(int arg) {
if (arg < 10) { value = arg; next_node = nullptr; }
else { value = arg % 10; next_node = new Digits(arg/10); }
}
};

int valueOrZero(Digits* node) { return node==nullptr ? 0 : node->value; }

Digits* nextOrNull(Digits* node) { return node==nullptr ? nullptr : node->next_node; }

string digitsToString(Digits* node) {
return node==nullptr ? "" : digitsToString(node->next_node) + to_string(node->value);
}

Digits* addTwoNumbers(Digits* node1, Digits* node2, int carry=0)
{
if ((node1==nullptr) & (node2==nullptr)) {
return(new Digits(carry));
}
else {
int tens=0;
int ones = valueOrZero(node1) + valueOrZero(node2) + carry;
if (ones >= 10) {
tens = ones/10;
ones = ones % 10;
}
Digits* answer = new Digits(ones);
answer->next_node = addTwoNumbers(nextOrNull(node1), nextOrNull(node2), tens);
return answer;
}
}

void testAdd(int val1, int val2) {
Digits *num1 = new Digits(val1);
Digits *num2 = new Digits(val2);
Digits *num3 = addTwoNumbers(num1, num2);
cout << digitsToString(num1) << "+" << digitsToString(num2) << " = " << digitsToString(num3) << endl;
}

int main(int argc, char* argv[]) {
testAdd(1,1);
testAdd(8,9);
testAdd(23,8);
testAdd(999,25);
}

1
ответ дан 30 марта 2018 в 12:03 Источник Поделиться