/
04543
/
alg-datastr
Обзор
Документация
Войти
/
04543
/
alg-datastr
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
linkedList.py
362 строки
11 KB
vakovalik
разворот связного списка
18 июн 2025, 22:49
18 июн 2025, 22:49
ca56f31
Код
Авторство
О чём код?
class Node: """Узел связанного списка""" def __init__(self, data): self.data = data self.next = None class LinkedList: """Взаимодействие со связанным списком""" def __init__(self): self.head = None def __len__(self): length = 0 current = self.head while current: length += 1 current = current.next return length def build(self, values): """Создаёт список""" for value in values: new_node = Node(value) if not self.head: self.head = new_node else: current = self.head while current.next: current = current.next current.next = new_node def get_at(self, index): """Возвращает элемент по индексу""" current = self.head count = 0 while current: if count == index: return current.data count += 1 current = current.next return None def set_at(self, index, data): """Меняет элемент по индексу""" current = self.head count = 0 while current: if count == index: current.data = data return count += 1 current = current.next def delete_at(self, index): """Удаляет элемент по индексу""" if index < 0: return current = self.head prev = None count = 0 if index == 0: self.head = current.next return while current: if count == index: prev.next = current.next current = None return prev = current current = current.next count += 1 def insert_at(self, index, data): """Вставляет новый элемент в список по индексу""" if index < 0: return new_node = Node(data) current = self.head prev = None count = 0 if index == 0: new_node.next = self.head self.head = new_node return while current: if count == index: prev.next = new_node new_node.next = current return prev = current current = current.next count += 1 prev.next = new_node def delete_last(self): """Удаляет последний элемент""" if not self.head: return current = self.head prev = None while current.next: prev = current current = current.next if prev: prev.next = None else: self.head = None def delete_first(self): """Удаляет первый элемент""" if self.head: self.head = self.head.next def insert_first(self, data): """Вставляет элемент в начало""" new_node = Node(data) new_node.next = self.head self.head = new_node def insert_last(self, data): """Вставляет элемент в конец""" new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node def find(self, key): """Находит первый элемент по значению и возвращает его""" current = self.head while current: if current.data == key: return current current = current.next return None def find_min(self): """Находит минимальное значение в списке""" if not self.head: return None current = self.head min_value = current.data while current: if current.data < min_value: min_value = current.data current = current.next return min_value def find_max(self): """Находит максимальное значение в списке""" if not self.head: return None current = self.head max_value = current.data while current: if current.data > max_value: max_value = current.data current = current.next return max_value def find_next(self, key): """Находит следующий элемент после заданного значения""" current = self.head while current: if current.data == key: return current.next current = current.next return None def find_prev(self, key): """Находит предыдущий элемент перед заданным значением""" current = self.head prev = None while current: if current.data == key: return prev prev = current current = current.next return None def find_middle(self): """Находит середину списка (значение)""" slow = self.head fast = self.head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow.data def get_middle(self, head): """Находит середину списка (элемент)""" slow = head fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def find_kth(self, k): """Находит k-й элемент с конца""" current = self.head current_k = self.head while k: current_k = current_k.next k-=1 while current_k: current_k = current_k.next current = current.next return current def define_cycle(self): """Определяет есть ли цикл в списке и находит его длину""" slow = self.head fast = self.head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: current = slow len = 0 while current: current = current.next len += 1 if current == slow: break return len return False def merge_sort(self): """Рекурсивная сортировка слиянием""" def merge(left, right): """Сливает два отсортированных списка""" if left is None: return right if right is None: return left if left.data <= right.data: result = left result.next = merge(left.next, right) else: result = right result.next = merge(left, right.next) return result def sort(head): """Рекурсивная сортировка""" if head is None or head.next is None: return head middle = self.get_middle(head) next_to_middle = middle.next middle.next = None left = sort(head) right = sort(next_to_middle) return merge(left, right) self.head = sort(self.head) def insertion_sort(self): dummy = Node(0) current = self.head while current: prev = dummy next_node = current.next while prev.next and prev.next.data < current.data: prev = prev.next current.next = prev.next prev.next = current current = next_node self.head = dummy.next def reverse(self): """Разворачивает весь связный список""" prev = None current = self.head while current: next_node = current.next current.next = prev prev = current current = next_node self.head = prev def reverse_list(self, head): """Разворачивает список начиная с head и возвращает новый head""" prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev def reverse_from_middle(self): """Разворачивает левую и правую части списка относительно середины""" if not self.head or not self.head.next: return middle = self.get_middle(self.head) left_head = self.head right_head = middle.next middle.next = None prev = None current = self.head while current and current != middle: prev = current current = current.next if prev: prev.next = None left_reversed = self.reverse_list(left_head) right_reversed = self.reverse_list(right_head) self.head = left_reversed current = self.head while current and current.next: current = current.next if current: current.next = middle middle.next = right_reversed def display(self): current = linked_list.head while current: print(current.data, end=" ") current = current.next # Использование linked_list = LinkedList() linked_list.build(list(map(int, input("Введите элементы списка через пробел: ").split()))) print("Связанный список: ", end="") linked_list.display() print("\nОтсортированный связанный список: ", end="") linked_list.merge_sort() linked_list.display() print("\nРазвернутый связанный список: ", end="") linked_list.reverse() linked_list.display() print("\nРазвернутый от середины связанный список: ", end="") linked_list.reverse_from_middle() linked_list.display()