Переупорядочение связанного списка в 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()