✅ Решение задачи 143

Time: O(n)
Space: O(1)

📝 Идея
▫️С помощью двух указателей slow и fast находим середину списка
▫️Переворачиваем вторую часть списка знакомым алгоритмом
▫️Теперь остается только последовательно брать элементы из первой части списка и из перевернутой второй

#solution143

🟢 Easy
141. Linked List Cycle

📃 Дан связанный список, определите есть ли в нем цикл, используя O(1) памяти

Подсказка: используйте два указателя

35/200
#easy
#leetcode141

✅ Решение задачи 141

Time: O(n)
Space: O(1)

📝 Идея
▫️Используем два указателя slow и fast:
- slow сдвигаем на одну позицию вперед
- fast сдвигаем на две позиции вперед
▫️Если в списке есть цикл, то они обязательно в один момент встретятся

#solution141

🟡 Medium
2. Add Two Numbers

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

Подсказка: реализуйте обычное сложение столбиком

36/200
#medium
#leetcode2

✅ Решение задачи 2

Time: O(n)
Space: O(1)

📝 Идея
▫️Так как списки уже даны в обратном порядке, удобно реализовать обычное сложение столбиком
▫️Если при сложении двух цифр сумма оказалась больше 10, запоминаем единицу и используем ее дальше

#solution2

🟡 Medium
287. Find the Duplicate Number

📃 Дан массив целых чисел, содержащий n + 1 целые числа, где каждое целое число находится в диапазоне [1, n] включительно.

В массиве есть только одно повторяющееся число, верните его

Необходимо решить задачу, не изменяя массив и используя только O(1) память

Подсказка: задача сводится к нахождению цикла, как в связанном списке

37/200
#medium
#leetcode287

✅ Решение задачи 287

Time: O(n)
Space: O(1)

📝 Идея
▫️Используем два указателя: slow передвигаем на 1 позицию вперед, fast — на две
▫️Теперь, когда знаем их точку пересечения — запускаем новый указатель с начала массива и также передвигаем на одну позицию одновременно со slow
▫️Данный алгоритм всегда будет указывать на элемент, в котором образуется цикл

#solution287

🔴 Hard
23. Merge k Sorted Lists

📃 Вам дан массив k связанных списков lists, где каждый отсортирован в порядке возрастания.

Объединить все связанные списки в один отсортированный связанный список и вернуть его.

Подсказка: попарно реализовывайте слияние двух списков, пока не останется один

38/200
#hard
#leetcode23

✅ Решение задачи 23

Time: O(nlog(k))
Space: O(1)

📝 Идея
▫️Проходимся по массиву списков с таким шагом, чтобы каждый раз попарно соединять оставшиеся списки, то есть по принципу сортировки слиянием
▫️Для соединения отсортированных списков используем знакомый алгоритм

#solution23

🔴 Hard
25. Reverse Nodes in k-Group

📃 Дан связанный список, переставьте узлы списка и верните измененный список

Правила перестановки:
Дано число k - меньшее или равное длине связанного списка, переверните узлы связанного списка через каждые k узлов
Если число узлов не кратно k, то оставшиеся узлы оставьте такими, какие они есть.

Подсказка: передвигайте указатель на k вперед и используйте уже знакомый алгоритм

39/200
#hard
#leetcode25

✅ Решение задачи 25

Time: O(n)
Space: O(1)

📝 Идея
▫️Функцией getKNode проходим k узлов вперед
▫️Далее используем алгоритм переворачивания списка, но изначальной ссылкой на предыдущей элемент делаем KNode
▫️Также используем две переменные groupPrev и groupNext для сохранения нужных ссылок на части списка

#solution25

Класс TreeNode:

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) {
          this.val = val;
      }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

🟢 Easy
226. Invert Binary Tree

📃 Дан root - корень двоичного дерева, инвертируйте его и верните root

Подсказка: используйте рекурсию

40/200
#easy
#leetcode226

✅ Решение задачи 226

Time: O(n)
Space: O(1)

📝 Идея
▫️Заменяем ссылку на левую ветвь — ссылкой на правую, затем рекурсией делаем тоже самое для оставшихся узлов

#solution226

🟢 Easy
543. Diameter of Binary Tree

📃 Дан root — корень двоичного дерева, верните длину его диаметра

Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь необязательно проходит через root

Подсказка: используйте рекурсию, проверяя каждый узел на возможный максимальный диаметр

41/200
#easy
#leetcode543

✅ Решение задачи 543

Time: O(n)
Space: O(n)

📝 Идея
▫️Используя рекурсию, доходим до конца дерева для правой и левой ветки, считая при этом глубину
▫️В каждом узле делаем проверку на возможный максимум, складывая глубины правой и левой веток
▫️Для функции dfs возвращаем максимум из left и right, чтобы всегда считать наибольшую длину диаметра

#solution543

🟢 Easy
110. Balanced Binary Tree

📃 Дано бинарное дерево, определите, является ли оно
сбалансированный по высоте.

Сбалансированное дерево — это дерево, в котором глубина двух поддеревьев каждого узла не отличается более чем на единицу.

Подсказка: используйте рекурсию, проверяя каждый узел на сбалансированность

42/200
#easy
#leetcode110

✅ Решение задачи 110

Time: O(n)
Space: O(n)

📝 Идея
▫️Используя рекурсию, доходим до конца дерева для правой и левой ветки, считая при этом глубину
▫️В каждом узле делаем проверку на сбалансированность, при этом, если одно из поддеревьев несбалансированное, также возвращаем -1, так как для положительного ответа все узлы дерева должны быть сбалансированы

#solution110

🟢 Easy
572. Subtree of Another Tree

📃 Даны корни двух двоичных деревьев root и subRoot, вернуть true, если в root существует поддерево с той же структурой и значениями узлов, как в subRoot

Поддерево бинарного дерева — это дерево, состоящее из узла и всех его потомков. Дерево также можно рассматривать как поддерево самого себя.

Подсказка: рекурсивно проверяйте каждый узел на возможное поддерево

43/200
#easy
#leetcode572

✅ Решение задачи 572

Time: O(nm)
Space: O(n)

📝 Идея
▫️Проходимся по всему дереву root и для каждого узла функцией sameTree делаем проверку на идентичность данного поддерева и subroot
▫️Функция sameTree просто проходится по обоим деревьям, сравнивая значения

#solution572

🟡 Medium
235. Lowest Common Ancestor of a Binary Search Tree

📃 Для заданного двоичного дерева найдите узел наименьшего общего предка двух заданных узлов p и q

Наименьший общий предок — ближайший узел, который имеет p и q в качестве потомков (также узел может быть потомком самого себя)

Подсказка: используйте тот факт, что слева от узла находятся значения меньше, а справа больше

44/200
#medium
#leetcode235