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

Question

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

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()

Есть идеи?

Answer 1

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

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

 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.

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

Answer 2

Меня огорчает, что структура данных "дважды связанный список-с-нулевым заголовком" больше не завоевывает популярность. В этой структуре каждый узел указывает на свои предыдущие и следующие элементы, и , сам список начинается с нулевого узла, который является только заголовком, и фактически никогда не содержит никаких данных. В исходном пустом списке указатели next и prev нулевого заголовка указывают на сам узел. С этой простой инициализацией остальная часть связывающего и не связывающего кода может быть реализована практически без каких-либо вещей, «если next не равен None» или «если prev не является None» - указатели next и prev never None ! Посмотрите на простоту add_before, add_after и remove, а затем посмотрите, как легко сделать переупорядочение. Как и в deque, вставка в начале или конце списка - это 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()