Отсортируйте односвязный список по возрастанию сортировкой выбором, переставляя узлы, а не значения. Напишите sort_nodes(head): функция возвращает новую голову. Новые узлы не создаются, поле value не меняется, узлы с равными значениями сохраняют исходный порядок.
head = Node(4, Node(1, Node(3, Node(1))))
head = sort_nodes(head) # 1 → 1 → 3 → 4 (сначала та единица, что шла раньше)sorted.Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
class Node:
"""Узел односвязного списка."""
def __init__(self, value: int, next: "Node | None" = None) -> None:
self.value = value
self.next = next
def sort_nodes(head: Node | None) -> Node | None:
"""Сортирует список выбором, переставляя узлы; возвращает новую голову."""
# ваш код
raise NotImplementedErrorВывод обрезан: показаны первые строки.
def _build(values: list[int]) -> Node | None:
head = None
for v in reversed(values):
head = Node(v, head)
return head
def _nodes(head: Node | None) -> list[Node]:
nodes = []
while head is not None:
nodes.append(head)
assert len(nodes) <= 10_000, "в списке цикл — у какого-то узла не обнулён next"
head = head.next
return nodes
def _check(values: list[int]) -> None:
head = _build(values)
original = _nodes(head)
result = _nodes(sort_nodes(head))
got = [n.value for n in result]
expected = sorted(values)
assert got == expected, f"{values}: получено {got}, ожидалось {expected}"
assert len(result) == len(original), f"узлов было {len(original)}, стало {len(result)}"
ids = {id(n) for n in original}
assert all(id(n) in ids for n in result), "в результате есть новые узлы — нужно переставлять старые"
# равные значения — в исходном порядке
position = {id(n): i for i, n in enumerate(original)}
for a, b in zip(result, result[1:]):
if a.value == b.value:
assert position[id(a)] < position[id(b)], f"равные значения {a.value} поменялись местами"
def test_example():
"""Пример: 4 → 1 → 3 → 1"""
_check([4, 1, 3, 1])
def test_empty():
"""Пустой список → None"""
got = sort_nodes(None)
assert got is None, f"ожидалось None, получено {got!r}"
def test_single():
"""Один узел"""
_check([9])
def test_sorted_and_reverse():
"""Уже отсортированный и обратный порядок"""
_check([1, 2, 3, 4, 5])
_check([5, 4, 3, 2, 1])
def test_min_in_the_middle_and_end():
"""Минимум в середине и в хвосте"""
_check([5, 6, 0, 7, 8])
_check([5, 6, 7, 8, 0])
def test_duplicates_stable():
"""Много равных значений — порядок равных сохраняется"""
_check([2, 1, 2, 1, 2, 1, 0, 2])
def test_all_equal():
"""Все значения одинаковые"""
_check([3, 3, 3, 3])
def test_longer():
"""200 узлов"""
_check([(i * 71) % 97 for i in range(200)])Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 sort_linked_list.py — тесты те же, результат покажет ✓ / ✗ и итог.
Это та же сортировка выбором: найти минимальный узел, вынуть его из исходного списка, приписать в конец результата. Повторять, пока исходный список не опустеет.
Чтобы вынуть узел из середины односвязного списка, нужен предыдущий узел. Ищите минимум, запоминая и узел, и его предшественника.
Держите указатель на хвост результата, чтобы добавлять в конец за O(1). Не забудьте обнулить next у добавленного узла.
class Node:
"""Узел односвязного списка."""
def __init__(self, value: int, next: "Node | None" = None) -> None:
self.value = value
self.next = next
def sort_nodes(head: Node | None) -> Node | None:
"""Сортирует список выбором, переставляя узлы; возвращает новую голову."""
result_head = result_tail = None
while head is not None:
# ищем первый минимальный узел и его предшественника
best_prev, best = None, head
prev, cur = head, head.next
while cur is not None:
if cur.value < best.value:
best_prev, best = prev, cur
prev, cur = cur, cur.next
# вынимаем его из исходного списка
if best_prev is None:
head = best.next
else:
best_prev.next = best.next
best.next = None
# приписываем в конец результата
if result_tail is None:
result_head = result_tail = best
else:
result_tail.next = best
result_tail = best
return result_head