Сложность: medium
Вам дана голова односвязного списка. Список можно представить в следующем виде:
L0 → L1 → … → Ln - 1 → Ln
Переупорядочите список так, чтобы он принял следующую форму:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы.
Пример:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
👨💻 Алгоритм:
1⃣Нахождение середины списка и разделение его на две части:
Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине.
Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка.
2⃣Реверс второй половины списка:
Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка.
Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка.
3⃣Слияние двух частей списка в заданном порядке:
Начните с головы первой части списка (first) и головы реверсированной второй части (second).
Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки.
Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся.
😎 Решение:
function reorderList($head) {
if ($head === null) return;
$slow = $head;
$fast = $head;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next;
$fast = $fast->next->next;
}
$prev = null;
$curr = $slow;
while ($curr !== null) {
$tmp = $curr->next;
$curr->next = $prev;
$prev = $curr;
$curr = $tmp;
}
$first = $head;
$second = $prev;
while ($second->next !== null) {
$tmp = $first->next;
$first->next = $second;
$first = $tmp;
$tmp = $second->next;
$second->next = $first;
$second = $tmp;
}
}Ставь 👍 и забирай 📚 Базу знаний