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

有任何想法吗？

有时最好的办法是首先考虑“最佳解决方案有多快？”这看起来很明显 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.

正如 Matt 和 Jodaka 所指出的，如果允许使用奇数长度列表，您确实需要决定如何处理奇数长度列表。