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

Answer 2

有时候，最好的做法是先想一想“一个最优解会有多快？” 这看起来很明显是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.

正如Matt和Jodaka所提到的，你需要决定如何处理奇数长度的列表，前提是允许使用奇数长度的列表。