Переупорядочение связанного списка в Python

Я понимаю, что такая структура данных лучше выполняется со встроенным типом списка, но я пытаюсь понять это по академическим причинам. Учитывая, что у меня есть связанный список:

a -> b -> c -> d -> e -> f

Я хотел бы изменить ссылки на

b -> a -> d -> c -> f -> e

Другими словами, каждая пара переключается. Я использую эти два класса для создания связанного списка.

class Node: def __init__(self): self.cargo = None self.next = None class LinkedList: def __init__(self): self.cur_node = None def add_node(self, cargo): new_node = Node() new_node.cargo = cargo new_node.next = self.cur_node self.cur_node = new_node def print_list(self): node = self.cur_node while node: print node.cargo node = node.next def reorder(self): # missing code here! ll = LinkedList() ll.add_node("a") ll.add_node("b") ll.add_node("c") ll.add_node("d") ll.add_node("e") ll.add_node("f") ll.reorder() ll.print_list() 

Есть идеи?

2 Solutions collect form web for “Переупорядочение связанного списка в Python”

Иногда лучше всего сначала подумать: «Как быстро будет оптимальное решение?» Это кажется довольно O ( длина ), поэтому что-то, что проходит через список, желательно один раз, будет примерно таким же хорошим, как вы можете.

Учитывая это, вы, вероятно, найдете лучший выбор. В псевдокоде это было бы

  get the first element in left get the second element in right append them to a new list as right->left repeat until you run out of list. 

Как отмечает Мэтт и Джодака, вам нужно решить, что делать с списком нечетной длины, если разрешен список нечетной длины.

Меня огорчает то, что структура данных с двойным соединением-списком с нулевым заголовком больше не попадала. В этой структуре каждый узел указывает на свой предыдущий и следующий элементы, а сам список начинается с нулевого узла, который является только заголовком и никогда не имеет никаких данных. В исходном пустом списке указатель нулевого заголовка и указатель предшествующего узла указывают на сам узел. С помощью этой простой инициализации остальная часть связующего и разуплотняющегося кода может быть реализована с почти любыми «если следующий не является ни одним» или «если предыдущий не является ни одним» – следующее и предыдущие указатели никогда не являются ни одним! Посмотрите на простоту add_before, add_after и удалите, а затем посмотрите, как легко выполняется переупорядочение. Как и дека, вставка в начале или конце списка – O (1) – просто self.header.add_after чтобы вставить в голову, или self.header.add_before чтобы вставить в конец.

 class Node: def __init__(self): self.cargo = None self.next = self self.prev = self def add_after(self, other): other.next = self.next other.prev = self self.next.prev = other self.next = other def add_before(self, other): other.next = self other.prev = self.prev other.prev.next = other self.prev = other class LinkedList: def __init__(self): self.header = Node() def __bool__(self): return self.header.next != self.header __nonzero__ = __bool__ # for older Pythons def empty(self): return not self def add_node(self, cargo): new_node = Node() new_node.cargo = cargo self.header.add_before(new_node) @staticmethod def pop(node): node.prev.next = node.next node.next.prev = node.prev node.next = node.prev = node return node def print_list(self): node = self.header.next while node != self.header: print node.cargo node = node.next def reorder(self): node = self.header.next while node != self.header and node.next != self.header: node.add_before(self.pop(node.next)) node = node.next ll = LinkedList() ll.add_node("a") ll.add_node("b") ll.add_node("c") ll.add_node("d") ll.add_node("e") ll.add_node("f") ll.print_list() ll.reorder() ll.print_list() 
  • Фильтрация массива в Python с двумя условиями
  • Найти ближайшие индексы для одного массива против всех значений в другом массиве - Python / NumPy
  • дополнительный пустой элемент при удалении элемента из кортежа
  • Списки / массивы Python: отключить отрицательную индексацию обертки в срезах
  • Как проверить, имеют ли перестановки равную четность?
  • Как создать массив numpy списков?
  • Уменьшить доступ к отдельным элементам, чем для списков
  • Как читать массив целых чисел из одной строки ввода в python3
  • Python - определение максимального значения во втором столбце вложенного списка
  •  
    Interesting Posts for Van-Lav

    Расширение документации документации Sphinx работает по-разному для вывода HTML и LaTeX?

    Передача строки в agege в файле agraph.py. Проблема с networkx и pygraphviz

    Pymongo aggregate: фильтр по количеству полей (динамический)

    установить выравнивание текста с расширенным текстом ctrl

    Почему функции всегда возвращают один и тот же тип?

    Anaconda3 2.4 с ошибкой установки python 3.5 (запись процедуры не найдена, Windows 10)

    Почему str.split не принимает аргументы ключевого слова?

    Как вставить значения «NULL» в базу данных PostgreSQL с помощью Python?

    Как мы должны проверять исключения с носом?

    Навигация вручную с помощью курсора через вложенные списки, только предоставляя «left ()» и «right ()» в качестве команд?

    Обновление словаря словарей в Python

    Альтернативы php для встроенного веб-программирования?

    Подсчет появления нескольких подстрок в панде

    Как обеспечить синтаксическую окраску Python внутри Webstorm?

    Есть ли простой способ добавить границу к ярлыкам Kivy, кнопкам, виджетам и т. Д. Без изображений?

    Python - лучший язык программирования в мире.