iBit: связанные списки
Вам даны два связанных списка, представляющих два неотрицательных числа. Цифры хранятся в обратном порядке, и каждый из их узлов содержит одну цифру. Добавьте два числа и верните их в виде связанного списка.
Ввод: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Вывод: 7 -> 0 -> 8
342 + 465 = 807
Убедитесь, что в выходном списке нет завершающих нулей
Итак, 7 -> 0 -> 8 -> 0 не является допустимым ответом, даже если значение по-прежнему равно 807.
Подход к решению:
Очень похоже на симуляцию математического процесса суммирования чисел. Вы суммируете цифры и поддерживаете перенос.
Подсказки:
1) Что делать, если один список короче другого? 1-›2 + 2-›3-›4-›5
2) Что делать, если в ответе больше цифр? 1 + 9
Глупые ошибки, которые я совершил при поиске окончательного решения:
- Возврат последнего указателя вместо указателя head после изменения списка
, например, возвращениеcat конец; - Пропущен случай, когда aиbдостигают конца, но есть перенос.
- Включите это здесь:
//Line 9: while (a || b || car) { and //Line 31: if (a || b || car) {
3. (строка 33, 34)
if (a || b || car) { c->next = (ListNode *)malloc(sizeof(ListNode)); c->val = 0; // c = c->next; // } The order of the last two statements was reverse!! and this was leading to wrong answer
Имея связанный список и значение x, разделите его так, чтобы все узлы, меньшие x, располагались перед узлами, большими или равными x.
Вы должны сохранить исходный относительный порядок узлов в каждом из двух разделов.
Например,
учитывая 1-›4-›3-›2-›5-›2 и x = 3,
вернуть 1-›2-›2-›4-›3-›5 .
Подход к решению 1:
- Создайте совершенно новый связанный список.
- Сделайте 2 сканирования данного списка: сначала вставьте меньшие элементы, а затем добавьте большие/равные элементы.
Источники ошибок:
1) Первоначально я создавал новый LL, сканируя исходный LL и создавая новый узел после проверки значения каждого узла (строки 20–24):
if (a->next) { // && a->next->val < b) { c->next = (ListNode *)malloc(sizeof(ListNode)); c = c->next; }
Не нужно этого делать, потому что мы уже знаем, что окончательный список будет иметь ту же длину, что и исходный.
2) Забыл:
//Line 29: a = head; This led to wrong answer.
3) Забыл вот это:
//Line 9 a = a->next; //infiniteLoop This led to this compiler message: "Memory Limit Exceeded. Your submission didn't complete in the allocated memory limit."
4) Этот оператор непосредственно перед последним оператором возврата (строка 37):
// c->next = NULL; Compiler message: "Segmentation fault" Invalid memory access!