Решить суммарно 50 задач на leetcode

Прорешал повторно задачу Remove Linked List Elements. Решить получилось самостоятельно.
Временная сложность алгоритма O(n), пространственная сложность O(1).

49 из 50

Прорешал задачу Reverse Linked List. Задача на разворот Linked List сломала мне мозг окончательно. Не встречал подобных задач ранее. Долго не мог понять как происходит этот самый разворот. Вообщем попробовал через дебаг в idea, чтобы посмотреть, что происходит с объектами, не зашло. Частичное понимание пришло, когда добавил на каждом шагу вывод данных в консоль; чтобы видеть изменения. Для меня сложность заключалась в том, что LinkedList он вроде и объект; как будто бы единичный экземпляр, но по факту имеет вложенную структуру. И фиксировать изменения этой вложенной структуры было довольно таки сложно и напряжно в уме. Когда я увидел, как меняются данные, я уловил суть этого алгоритма и стало полегче. Задача по итогу написанного кода кажется несложной, но по факту для меня очень сложная.

Временная сложность O(n), пространственная сложность O(1).

48 из 50
Прорешал задачу Remove Nth Node From End of List. Задача уровня медиум. Походу для карточки "Linked list" - это норма. Я понял само задание, где-то через час. Первоначальное решение базировалось на мысли "Я понял, что надо делать. Сейчас я это сделаю". А когда начались петляния кода из одного условия в другое, я начал осознавать, что тут, что-то не так. Слишком сложное решение получается. Да и ненадежное. Код получился кривой, один кейс прошел, а вот остальные провалились.

Полез в solution и стал смотреть решение, как за один проход по linked list написать корректный алгоритм. И тут до меня дошло, что задание было немного в другом. Изучая готовое решение, я никак не мог понять, как вообще можно было додуматься до этого решения. Путем перебора решений, кто-то подсказал, или может быть алгоритмическое мышление - это какая-то магия. Я смотрю на решение и у меня в голове начинают появляться указатели, ноды, и все это само по себе перемещается, а я просто беру этот визуал и выписываю на бумагу, посредством кода. Как это вообще работает, ума не приложу.

Временная сложность алгоритма O(n), пространственная сложность O(1).

47 из 50
Прорешал задачу Intersection of Two Linked Lists. Удалось придумать решение самостоятельно с использованием структуры данных HashSet. Временная сложность получилась O(n), пространственная сложность O(n).

Второй способ решения разобрал в solution. При таком способе решения пространственная сложность становится O(1). Т.е дополнительных структур данных создавать не нужно.

46 из 50

Прорешал задачу Linked List Cycle II. Похожа на предыдущую, за исключение того, что нужно вернуть головную ноду c которой начинается зацикленность. Тут то и начались проблемы, как эту ноду получить. В одном случае вроде как можно сделать return node.next, а в другом return node. По итогу такой подход оказался неверен. Нашел статью в гугле, где с помощью картинки и математических формул (вроде как простых) описывается подход к решению, стало понятно кодовое решение. После этого удалось задачу решить, при этом немного уловить суть подхода. Вторая задачу уровня медиум. Написание алгоритма к задаче сильно усложнилось).

Временная сложность O(n), пространственная сложность O(1);

ссылка на статью: https://site.ada.edu.az/~medv/acm/Leetcode/142-Lin...

Прорешал повторно задачу Linked List Cycle. Потупил около часа, понял что ничего придумать не получается. Нужно было использовать паттерн быстрый и медленный указатель. Моя проблема была в том, что в цикле while я проверял на null только следующую ноду, в быстром указателе а надо было текущию и следующую ноду в быстром указателе.

Временная сложность O(n), пространственная сложность O(1). Ощущение, что начал учить Java с нуля. Просто ничего не понятно).

45 из 50
Прорешал задачу Design Linked List. Нужно было реализовать самописный односвязный список (его методы). Удалось реализовать методы и покрыть базовые кейсы на leetcode. К сожалению остальные кейсы покрыть не удалось. Стал разбирать решения. Доработал методы. Пытался представить, как происходит итерация по связному списку. Задача оказалась довольно объемной.

Закончил блок Singly Linked List из карточки "LinkedList"

Прорешал повторно задачу Squares of a Sorted Array. Получилось быстро написать алгоритм.
Временная сложность O(n), пространственная сложность O(n) . Закончил карточку "Arrays 101". Осталась одна задача, которая по подписке. У меня пока подписки нет. Перешел на карточку с задачами по linkedList.

44 из 50
Прорешал задачу Find All Numbers Disappeared in an Array. Разобрал два подхода к решению задачи.

Первый подход: временная сложность: O(n), пространственная сложность O(1).

Второй подход: временная сложность: O(n), пространственная сложность O(n).