iBit: связанные списки

  1. Добавить два числа в виде списков

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

Ввод: (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

Глупые ошибки, которые я совершил при поиске окончательного решения:

  1. Возврат последнего указателя вместо указателя head после изменения списка
    , например, возвращениеcat конец;
  2. Пропущен случай, когда 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

2. Список разделов

Имея связанный список и значение 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!