🔴Hard
224. Basic Calculator

Company: 🏢🚖🖼

📝Дана строка s, представляющее выражение, состоящее из цифр и символов '+', '-', '(', ')', ' '.

Верните результат выражения

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

#leetcode224 | #hard #stack

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

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

💡 Идея
🟦проходим по строке:
➖если символ цифра
▫строим текущее число, учитывая, что оно может быть многозначным

➖если символ оператор ('+' и '-')
▫добавляем к результату текущее число, умноженное на ранее сохранённый знак
▫сбрасываем текущее число
▫обновляем знак в соответствии с оператором ('+' → 1, '-' → -1)

➖если символ открывающая скобка
▫сохраняем текущий результат и знак в стек — они понадобятся после вычисления выражения в скобках
▫обнуляем результат и знак, чтобы начать вычисление новой подформулы внутри скобок

➖если символ закрывающая скобка:
▫завершаем вычисление текущего числа (умножаем на знак и прибавляем к результату)
▫достаём из стека знак и результат до скобки
▫умножаем текущий результат на сохранённый знак и прибавляем результат до скобки

👩‍💻 Java Algo | #solution224

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

Представь очередь за билетами на концерт. Каждый человек знает, кто следующий и никто не оглядывается назад.

Если ты решаешь пропустить вперёд своего друга, ты просто говоришь: "Я теперь за тобой", а он запоминает, кто должен быть следующим. Так работает вставка — связи между людьми меняются, но сама очередь не двигается.

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

А вот если ты пришёл в конец очереди и хочешь найти друга где-то в середине, тебе придётся пройти ее всю по порядку, спрашивая каждого: "Кто следующий?", пока не дойдёшь до нужного человека. Потому что в этой очереди никто не пронумерован — доступ возможен только шаг за шагом. Так работает поиск.

В задачах класс односвязного списка представлен как:

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

🟦Принципы LinkedList
▫Узел
Каждый элемент состоит из двух частей: значение и ссылка на следующий узел

▫Голова (Head)
Список начинается с одного элемента — головы, именно с неё начинается обход всего списка

▫Последовательный доступ
Нельзя просто взять и перейти сразу, например, к пятому элементу. Нужно идти от головы, шаг за шагом — пока не дойдёшь. Это похоже на то, как ты читаешь книгу — перелистывая страницу за страницей

▫Вставка
Сначала надо дойти до нужного места, затем поменять ссылки

▫Удаление
Похоже на вставку: находишь нужный узел и просто перенаправляешь ссылку предыдущего элемента мимо него, на следующий

#linkedlist

🟢Easy
876. Middle of the Linked List

Company: 🔍📱🏢

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

💡: используйте быстрый указатель

#leetcode876 | #easy #linkedlist

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

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

💡 Идея
🟦Для решения использована техника двух указателей ("черепаха и заяц"):
▫один — медленный (slow), делает по одному шагу
▫второй — быстрый (fast), делает по два шага

🟦Получаем, что когда fast доходит до конца, slow всегда оказывается посередине в нужной позиции:
▫длина списка нечетная — ровно посередине
▫длина четная — на втором из двух средних узлов

👩‍💻 Java Algo | #solution876

🟢Easy
203. Remove Linked List Elements

Company: 🔍📱📱

📝Дан cвязный список и целое число val, удалите из списка все узлы, имеющие значение равное val

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

#leetcode203 | #easy #linkedlist

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

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

💡 Идея
🟦чтобы удалить текущий узел, значение которого равно val, необходимо ссылку предыдущего узла перенаправить через текущий: prev.next = curr.next, иначе просто передвинуть предыдущий узел: prev = curr

🟦но, что, если голова заданного списка так же будет удалена, как тогда вернуть ответ?

🟦для этого в начале введен вспомогательный узел sentinel с ссылкой на начало заданного списка, в конце sentinel.next указывает на обновленнный список

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

👩‍💻 Java Algo | #solution203

🟢Easy
160. Intersection of Two Linked Lists

Company: 🚖📱🏢

📝Даны два связных списка A и B, вернуть узел, в котором они пересекаются. Если такого узла нет, вернуть null

Попробуйте написать решение, используя O(1) памяти

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

#leetcode160 | #easy #linkedlist

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

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

💡 Идея
🟦Найти пересечение двух списков было бы проще, если бы их длины были равны, тогда мы бы просто прошли по обоим спискам одновременно, пока не встретили бы пересечение

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

🟦Но есть более элегантный способ:

➖создаем два указателя: currA и currB и одновременно передвигаем их вперед

➖если один указатель дошёл до конца своего списка, он переходит в начало другого. То есть currA сначала проходит список A, затем список B, а currB наоборот

➖если указатель равны, прекращаем цикл и возвращаем ответ

🟦Почему это работает?
➖пусть длина списка A – a, B – b, тогда указатель сurrA пройдет a + b, а currB b + a

➖в результате перехода одного указателя на соседний список, они оба проходят a + b, поэтому списки гарантированно синхронизируются по длине и указатели либо встречаются в точке пересечения, либо оба становятся null

👩‍💻 Java Algo | #solution160

🟡Medium
24. Swap Nodes in Pairs

Company: 🏢🅰️🏢

📝Дан связный список, поменяйте местами каждые два соседних узла. Решите задачу, не изменяя значений в узлах списка

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

#leetcode24 | #medium #linkedlist

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

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

💡 Идея
🟦cоздаем вспомогательные узлы sentinel и prev, а затем проходим по списку, пока доступно два узла: текущий и следующий

🟦на каждом шаге последовательно меняем ссылки, держа в голове результат, который хотим получить. Разберем на примере prev -> 1 -> 2 -> 3:

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

▫меняем ссылку с предыдущего узла на второй, так как после перестановки он будет идти после него: prev -> 2

▫ссылку на следующий элемент от первого узла перекидываем через второй: 1 -> 3

▫и наконец, ссылку на следующий элемент от второго узла назначаем на первый узел, в итоге получаем: prev -> 2 -> 1 -> 3

▫далее обновляем prev на первый узел и переходим на следующую пару

👩‍💻 Java Algo | #solution24

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

#figure #linkedlist

🟡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