🟡Medium
61. Rotate List

Company: 🔍🏢📱

📝Дан связный список, поверните его на k позиций вправо

💡: переместите последние k узлов списка в начало, поменяв нужные ссылки на границах

#leetcode61 | #medium #linkedlist

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

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

💡 Идея
🟦Чтобы повернуть список на k позиций вправо, необходимо взять k последних узлов и поставить их перед началом. Поэтому нужно найти этот блок и поменять ссылки на его границах

🟦Для этого пройдем указателем curr до конца списка, заодно посчитаем его длину и избавимся от лишних поворотов, взяв остаток от деления для k

🟦сurr в данный момент находится в конце блока k, поэтому поменяем ссылку данного узла на начало списка, тем самым поставим данный блок перед началом

🟦далее необходимо оказаться перед началом блока k, чтобы завершить алгоритм, поэтому проходим указателем curr расстояние (n – k) и оказываемся в нужном месте

🟦далее запоминаем следующий узел для ответа (начало нового списка) и ссылаем текущий узел на null (конец нового списка)

👩‍💻 Java Algo | #solution61

🟡Medium
86. Partition List

Company: 📱🅰️🏢

📝Дан связный список и значение x, разбейте его так, чтобы все узлы меньше x располагались перед узлами, большими или равными x.

Необходимо сохранить исходный относительный порядок узлов в каждом из двух разделов

💡: связывайте нужные значения в отдельные списки, а затем соедините их

#leetcode86 | #medium #linkedlist

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

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

💡 Идея
🟦Для решения будем распределять узлы с соответствующими значениями в разные списки, а затем соединим их

🟦Инициализируем вспомогательные узлы по одному в начало каждого списка:
➖lessDummy для элементов <x,
➖greaterDummy для элементов >=x.
Они помогут удобно собирать списки без отдельной обработки первого элемента

🟦Далее проходим по списку и на каждом шаге:
➖если значение текущего узла меньше x — цепляем его в список less и передвигаем данный указатель
➖если больше или равно x — цепляем его в список greater и также передвигаем данный указатель

🟦После прохода соединяем списки в правильной последовательности:
➖конец "меньшего" списка ссылаем на начало "большего"
➖конец "большего" списка ссылаем на null

🟦В конце возвращаем узел ответа, как начало "меньшего" списка

👩‍💻 Java Algo | #solution86

🟡Medium
92. Reverse Linked List II

Company: 🔍📱🅰️

📝Дан связный список и два целых числа left и right (left <= right). Необходимо развернуть элементы списка на позициях от left до right включительно

💡: реализуйте алгоритм reverseList для [left, right], но сохраните узел перед left

#leetcode92 | #medium #linkedlist

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

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

💡 Идея
🟦Решение состоит в том, чтобы применить знакомый алгоритм переворачивания списка на промежутке [left, right], поэтому ведем подсчет узлов (n) и, если n стал равен left, применяем данный алгоритм, пока n меньше right

🟦Но, после такого применения алгоритма, остаются неправильные ссылки по краям перевернутого списка, поэтому во время прохода по списку, пока n < left, ведем вспомогательный узел dummy, который остановится прямо перед left

🟦Благодаря dummy, теперь можно выставить нужные ссылки — узел left ссылаем на следующий после right: dummy.next.next = curr, а узел перед left ссылаем на right: dummy.next = prev

🟦В конце возвращаем исходную голову списка, если left > 1, иначе dummy.next, так как голова списка в таком случае также будет изменена

👩‍💻 Java Algo | #solution92

🖼Иллюстрация алгоритма к задаче 92

Пример: head = [1,2,3,4,5], left = 2, right = 4

#figure #linkedlist

❗️Обновление

Теперь доступен отдельный канал JA Roadmap c полной навигацией по всем задачам.

В нем можно очень удобно повторять нужные темы, сразу переходя к постам.

Вскоре еще добавится полная RoadMap по самым нужным задачам для прохождения собеседования, а также топ задач в конкретные компании

Не пропускайте ➡️ JA Roadmap

🟡Medium
148. Sort List

Company: 📱📱🔍

📝Дан связный список, отсортируйте его в порядке возрастания

💡: рекурсивно делите список пополам и сортируйте каждую его часть, а затем объедините их

#leetcode148 | #medium #linkedlist

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

Time: O(nlogn)
Space: O(logn)

💡 Идея
🟦Для решения реализуем сортировку слиянием: рекурсивно делим список пополам, сортируем каждую часть, а затем собираем вместе

🟦Чтобы разделить список, находим его середину и изменяем его ссылку на null, перед этим запомнив следующий узел, который будет являться началом второй половины

🟦Для этого реализуем функцию getMid с идеей, как в этом решении, но здесь при четной длине возвращаться будет первый средний узел (fast изначально ставим на head.next):

private ListNode getMid(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

return slow;
}

🟦Далее рекурсивно вызываем исходную функцию для каждой части, после чего получаем их отсортированными. Теперь можно их соединить, используя функцию merge:

➖проходим по обоим спискам, пока их указатели не равны null, выбираем наименьший узел из двух текущих и добавляем его в результат

➖после цикла присоединяем остаток одного из списков

🟦В итоге список последовательно делится на всё более мелкие части, пока не дойдет до одного узла, затем с помощью функции merge все части постепенно соединяются в один отсортированный список и в результате мы получаем правильный ответ

👩‍💻 Java Algo | #solution148

🔴Hard
23. Merge k Sorted Lists

Company: 🏢📱❤️

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

Объедините все списки в один отсортированный и верните его

💡: соединяйте списки попарно с шагом, который постепенно увеличивается в 2 раза

#leetcode23 | #hard #linkedlist

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

Time: O(nlogk)
Space: O(1)

💡 Идея
🟦Одним из простых решений могло стать последовательное слияние всех списков с первым, но тогда бы мы получили сложность по времени O(nk), что не так хорошо

🟦Вместо этого можно соединять все списки парами с шагом step, пока данный шаг меньше длины массива

🟦В начале step равен 1, то есть мы соединяем только текущий и следующий список: merge(list[i], list[i + step]), но далее — после каждого прохода по массиву, мы увеличиваем его в два раза, чтобы объединять уже более длинные промежуточные списки

🟦При этом шаг i прохода по массиву должен быть в два раза больше step, чтобы “переступать” через уже объединенные списки, не затрагивая их повторно

🟦Таким образом, массив списков делится и объединяется по парам logk раз и в итоге мы получаем сложность O(nlogk)

👩‍💻 Java Algo | #solution23

🖼Иллюстрация алгоритма к задаче 23

#figure #linkedlist

🔴Hard
25. Reverse Nodes in k-Group

Company: 🔍🅰️🚀

📝Дан односвязный список и целое число k. Требуется переворачивать список по группам из k узлов.

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

💡: передвигайте указатель на k вперед для отделения группы узлов, после чего используйте алгоритм переворачивания

#leetcode25 | #hard #linkedlist

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

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

💡 Идея
🟦В основе решения — вспомогательная функция getKNode, которая возвращает k-й узел от начала текущей группы. Если такой узел существует, значит группа полная и её можно перевернуть знакомым алгоритмом

🟦Перед разворотом сохраняем начало следующей группы: kNode.next и используем его как начальное значение для prev, чтобы сразу соединить текущую группу с оставшейся частью списка

🟦После разворота соединяем предыдущую часть списка с новой головой группы: prevPart.next = kNode, затем сдвигаем prevPart к концу текущей уже перевёрнутой группы

🟦Таким образом, список обрабатывается по частям длиной k, каждая из которых переворачивается и аккуратно соединяется с остальными, обеспечивая правильную структуру

👩‍💻 Java Algo | #solution25

➡️ Стартуем тему бинарного поиска

Представь, что кто-то загадал число от 1 до 100, и ты пытаешься его угадать, задавая вопросы: "твоё число больше этого?" или "меньше?".

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

Спрашиваешь: "Твоё число больше 50?":
▫Если да — значит, всё, что меньше или равно 50, можно забыть. Теперь ты ищешь только в диапазоне от 51 до 100.
▫Если нет — значит, загаданное число находится где-то между 1 и 49.

Теперь снова берёшь середину нового диапазона — например, 75, и повторяешь. С каждым вопросом ты уменьшаешь количество возможных вариантов в два раза и быстро приближаешься к загаданному числу.

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

Пример кода бинарного поиска заданного числа target в массиве (задача):

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return -1;
    }
}

📎Обратите внимание, что для вычисления mid используется l + (r - l) / 2, вместо привычного (l + r) / 2. Это нужно для того, чтобы избежать переполнения int при больших значениях l и r.

#binarysearch

🟢Easy
35. Search Insert Position

Company: 📱🏢🚖

📝Дан отсортированный массив различных целых чисел и значение target. Верните индекс вставки target в массив.

Вам необходимо написать алгоритм со сложностью O(logn) по времени

💡: определите какой указатель бинарного поиска будет указывать на нужную позицию после цикла

#leetcode35 | #easy #binarysearch

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

Time: O(logn)
Space: O(1)

💡 Идея
🟦Назначаем границы начального диапазона: l = 0, r = nums.length – 1

🟦Начинаем поиск, пока границы находятся в правильном отношении: l <= r:
➖находим середину: mid = l + (r - l) / 2

➖сравниваем nums[mid] с target:
▫если nums[mid] < target: значит target должен быть правее, поэтому сдвигаем левую границу: l = mid + 1
▫иначе target должен быть на этой позиции или левее, значит: r = mid – 1

🟦когда цикл завершён, l указывает на позицию вставки:
➖если target есть в массиве — это будет индекс его вхождения
➖если нет — это место, куда его нужно вставить, чтобы массив остался отсортированным

👩‍💻 Java Algo | #solution35

🟢Easy
69. Sqrt(x)

Company: 📱📱📱

📝Дано неотрицательное целое число x, вернуть квадратный корень x, округленного вниз до ближайшего целого числа.

Не допускается использование встроенных функций

💡: ищите ответ в диапазоне от 2 до x / 2

#leetcode69 | #easy #binarysearch

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

Time: O(logx)
Space: O(1)

💡 Идея
🟦Если x равен 0 или 1, сразу возвращаем его, так как корень равен самому числу

🟦Установим начальные границы для бинарного поиска: l = 2, r = x / 2, так как квадратный корень числа x точно не больше x / 2 (если x > 1)

🟦Начинаем поиск, пока l <= r:
➖находим среднее значение между l и r и его квадрат: square = (long) mid * mid, используя приведение к long, чтобы избежать переполнения

➖если square == x, найден точный корень — сразу возвращаем mid
➖если square < x, ищем большее значение, сдвигая левую границу: l = mid + 1
➖если square > x, ищем меньшее значение, сдвигая правую границу: r = mid - 1

🟦После завершения поиска, l будет указывать на первое число, квадрат которого превышает x, поэтому нужный результат — l - 1, то есть нужный по условию округлённый вниз квадратный корень

👩‍💻 Java Algo | #solution

🟢Easy
1539. Kth Missing Positive Number

Company: 🏢📱📱

📝Дан отсортированный массив arr натуральных чисел и целое число k.

Верните k-ое пропущенное число в этом массиве

💡: сравните исходный массив с массивом без отсутствующих чисел, чтобы понять, как передвигать указатели

#leetcode1539 | #easy #binarysearch