Partition List

Средняя№86фиктивная голова

Дан связный список и число x. Нужно переставить узлы так, чтобы все узлы со значением меньше x шли раньше узлов со значением x и больше, а внутри каждой группы узлы сохранили свой порядок. Вернуть начало. Наш пример: 6 → 1 → 9 → 4 → 2, x = 5 — ответ 1 → 4 → 2 → 6 → 9.

86 Partition ListРазбор · 1×

Пример: 6 → 1 → 9 → 4 → 2, x = 5. Старый список сверху; узлы меньше 5 переходят в средний ряд, остальные — в нижний.

nonelessHeadmoreHead61942less
ещё не дошлиnodeменьше 55 и большеответ

Фиктивный узел для узлов меньше 5: lessHead. less — последний узел этого списка, пока это сам фиктивный узел

01/34
сначала · назад · пуск · шаг
Скорость
1function partition(head, x):
2 lessHead = new node; less = lessHead
3 moreHead = new node; more = moreHead
4 node = head
5 while node is not none:
6 if node.val < x:
7 less.next = node
8 less = node
9 else:
10 more.next = node
11 more = node
12 node = node.next
13 more.next = none
14 less.next = moreHead.next
15 return lessHead.next
состояние
node
–
less
lessHead
more
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждый узел идёт в конец своего списка в том порядке, в каком их даёт старый список, поэтому обе группы сохраняют порядок.
  2. Благодаря двум фиктивным узлам пустой список не требует проверки: если узлов меньше x нет, lessHead.next просто станет первым узлом другого списка.
  3. Узлы переносятся, а не копируются, поэтому последний узел списка more сохраняет свой старый next. more.next = none обрезает его до того, как списки соединят; без этого ответ зацикливается.

Сложность

Время O(n): один проход, каждый узел переносим один раз. Память O(1): узлы те же, новые только два фиктивных.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.