Условие задачи "на пальцах"
🎯 Представьте ситуацию:
У вас есть цепочка друзей, стоящих в очереди. У каждого друга есть номер на футболке 🎽.
Ваша задача: перестроить очередь так, чтобы:
- Слева встали все, у кого номер меньше числа x 🔵
- Справа встали все, у кого номер больше или равен x 🔴
⚠️ Важное правило: Внутри каждой группы друзья должны остаться в том же порядке, в котором стояли изначально!
Формальное условие:
Дан связный список и число x. Разбейте список на две части:
- Все узлы со значением < x → должны идти первыми
- Все узлы со значением >= x → должны идти после
При этом относительный порядок элементов в каждой группе должен сохраниться!
Пример:
Вход: 1 → 4 → 3 → 2 → 5 → 2, x = 3
Группа < 3: [1, 2, 2] (в исходном порядке)
Группа >= 3: [4, 3, 5] (в исходном порядке)
Выход: 1 → 2 → 2 → 4 → 3 → 5
🔵🔵🔵 🔴🔴🔴
Как думать о решении?
Простая аналогия: "Две коробки" 📦
Представьте, что у вас есть две пустые коробки:
🔵 Коробка "Меньше" 🔴 Коробка "Больше или равно"
Вы идёте по цепочке друзей и каждого кладёте в нужную коробку:
Цепочка: [1] → [4] → [3] → [2] → [5] → [2]
[1] < 3? ✅ → в 🔵 коробку
[4] < 3? ❌ → в 🔴 коробку
[3] < 3? ❌ → в 🔴 коробку
[2] < 3? ✅ → в 🔵 коробку
[5] < 3? ❌ → в 🔴 коробку
[2] < 3? ✅ → в 🔵 коробку
🔵 Коробка: 1 → 2 → 2
🔴 Коробка: 4 → 3 → 5
Финал: соединяем коробки → 1 → 2 → 2 → 4 → 3 → 5 ✅
✨ Ключевая идея: Создаём два новых списка на лету, а в конце соединяем их!
Решение на Java с комментариями
Сложность алгоритма
⏱️ Время
O(n)
Проходим по списку ровно один раз
💾 Память
O(1)
Создаём только 4 указателя, не считая результата
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task86_partitionList/Solution.java