Переупорядочение связанного списка в 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 для множеств
  • TypeError: только целые массивы с одним элементом могут быть преобразованы в индекс 3
  • Найти ближайшие индексы для одного массива против всех значений в другом массиве - Python / NumPy
  • Как проверить, имеют ли перестановки равную четность?
  • Получить текущие координаты элемента на виджете Canvas с учетом его элемента управления?
  • Фильтрация массива в Python с двумя условиями
  • Python Список массивов np для массива
  • Как читать массив целых чисел из одной строки ввода в python3
  •  
    Interesting Posts for Van-Lav

    Использование numpy и pil для преобразования 565 (16 бит-цвет) в 888 (24-битный)

    Разделяйте сайты Django с общим брандмауэром аутентификации / регистрации

    scipy разреженная матрица: удалите строки, все элементы которых равны нулю

    Является ли python + = конкатенация строк плохой практикой?

    Как отслеживать рейтинги игроков?

    Применение фильтров jinja2 к блоку?

    Быстрый Pythonic способ превратить множество списков строк в списки поплавков при ловле ValueErrors

    Выберите действительный выбор ModelChoiceField

    Проверьте, находится ли float рядом с любым поплавком, хранящимся в массиве

    Python: использование scikit-learn для прогнозирования дает пустые прогнозы

    Запись на Python в файл с использованием stdout и fileinput

    Хороший язык для разработки игрового сервера?

    Получение тегов из экземпляров AWS с помощью boto

    чат-приложение. для django

    символ utf-8 в пути пользователя не позволяет импортировать модуль

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