эффективное добавление двух связанных списков в C

Question

У меня есть два связанных списка, представляющих цифры десятичных чисел в порядке от старшего к младшему.например, 4->7->9->6 и 5->7 Ответ должен быть 4->8->5->3 без обращения списков, потому что обращение списков приведет к снижению эффективности.

Я думаю о решении проблемы с использованием стека. Я перейдуи списки, и помещаем элементы данных в два отдельных стека. По одному для каждого связанного списка. Затем я складываю оба стека вместе и добавляю оба элемента, и если в результате получается двузначное число I 10 по модулю и сохраняю переносвременная переменная. Остаток сохраняется в узле, и перенос добавляется к следующей сумме и так далее.если два стека - s1 и s2, а список связанных результатов - res.

temp = 0;
res = (node*)(malloc(sizeof(node*));

while(s1->top!=-1 || s2->top!=-1)
{  
    temp = 0;
    sum = pop(s1) + pop(s2);
    n1 = (node*)(malloc(sizeof(node*));
    temp = sum/10;
    sum = sum%10;
    sum = sum+temp;
    n1->data = sum;
    n1->next = res;
    res = n1;
    free n1;
    //temp=0;
}

if((s1->top==-1)&&(s2->top==-1))
{
    return res;
}
else if(s1->top==-1)
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum + temp;
        temp = sum/10;
        sum = sum%10;
        n1 = (node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}
else
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum+temp;
        temp = sum/10;
        sum = sum%10;
        n1=(node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}

return res; 

Я много раз сталкивался с этой проблемой в вопросах интервью, но это лучшее решение, о котором я мог подумать.Если кто-то может прийти с чем-то более эффективным в CI будет очень рад.

Answer 1

Два прохода без стека:

• Получить длину двух списков.

• Создать список решений с одним узлом.Инициализируйте значение этого узла до нуля.Это будет держать цифру переноса.Установите указатель списка (назовите его указателем переноса) на местоположение этого узла.Установите указатель списка (назовите его указателем конца) на местоположение этого узла.

• Начиная с более длинного списка, для каждого лишнего узла свяжите новый узел с указателем конца иприсвойте ему значение лишнего узла.Установите указатель конца на этот новый узел.Если значение меньше 9, установите указатель переноса на новый узел.

• Теперь у нас остались оба указателя списка с одинаковым числом узлов в каждом.

• Пока списки не пусты ...

  • Свяжите новый узел с указателем конца и продвиньте указатель конца к этому узлу.

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

  • Добавить два значения вместе.

    1. Если значение больше девяти, установите значение value mod 10, увеличьте значение, содержащееся в узле указателя переноса, переместите указатель переноса на следующий узел.Если значение указателя переноса равно девяти, установите в ноль и перейдите к следующему узлу.

    2. Если значение равно девяти.Установить его.Больше ничего не делать.

    3. Если значение меньше девяти.Установить его.Установите указатель переноса на текущий узел.

• Когда вы закончите с обоими списками, проверьте, равно ли значение узла указателя решения нулю.Если это так, установите указатель решения на следующий узел, удалив ненужную лишнюю цифру.

Answer 2

Вот как бы я решил эту проблему:

Шаг 1: Сделайте проход в обоих связанных списках, найдите длины

скажем len(L1) = m and len(L2) = n

Шаг 2: Найти разницу длин

if ( m > n )
    d = m - n
else if ( n > m )
    d = n - m
else
    d = 0

Шаг 3: Переместить временный указатель d вперед по большему списку

Шаг 4: Теперь у нас есть два связанных списка для добавления, длина которых одинакова, поэтому добавьте их рекурсивно, сохраняя перенос.

Шаг 5: ( Примечание: , если (d == 0) не выполнять этот шаг)

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

if ( d > 0 )
    -Travel larger list till d positions recursively
    -Append sum = value_at_end + carry (update carry if sum >= 10) to output list at beginning
    -Repeat until difference is consumed

Примечание: Я решаю проблему так, как она была поставлена ​​передо мной, а не предлагая изменение базовой структуры данных.

Сложность времени:

1. Выполнение отдельных проходов в обоих списках для определения их длины: O(m+n)
2. Суммирование двух связанных списков одинакового размера (м -d и n) рекурсивно: O(n), предполагая m > n
3. Добавление оставшегося большего списка к списку вывода: O(d)

Итого: O( (m+n) + (n) + (d) ) ИЛИ O(m+n)

Сложность пространства:

1. шаг 2 сложности времени: O(n), пространство стека времени выполнения
2. шаг 3 сложности времени:O(d), пространство стека времени выполнения

Всего: O(n + d) ИЛИ O(n)

Answer 3

Я бы просто нашел общее значение каждого связанного списка отдельно, сложил их вместе, а затем преобразовал бы это число в новый связанный список. Поэтому преобразуйте 4-> 7-> 9-> 6 и 5-> 7 в целые числа со значениями 4796 и 57 соответственно. Сложите их вместе, чтобы получить 4853, затем преобразуйте это в связанный список, содержащий 4-> 8-> 5-> 3. Вы можете сделать преобразования с простой математикой.

Делать это по-своему было бы намного проще, если бы вы изменили способ представления чисел в первую очередь. Сделайте так, чтобы цифра единиц всегда была первой, за ней следовали цифры десятков, затем сотни и т. Д.

РЕДАКТИРОВАТЬ: Поскольку вы, очевидно, используете огромные числа: вы думали сделать их списки с двойной связью? Тогда вам не нужно будет обращать его вспять, по сути. Пройдите назад.

Answer 4

Если вы вдвойне связываете списки, вы можете добавить цифры и использовать обратные ссылки, чтобы узнать, куда поместить ваше значение. http://en.wikipedia.org/wiki/Doubly_linked_list

Answer 5

Использование стека не более эффективно, чем реверсирование списков (на самом деле - это реверсирование списков). Если ваш объект стека выделяется динамически, это не составляет большого труда, но если вы создадите его с помощью рекурсии вызова, вы легко получите Переполнение стека плохой сортировки. : -)