在Python中重新排序链接列表 [英] Re-ordering a Linked List in Python

问题描述

我意识到使用内置列表类型可以更好地完成这种数据结构，但是出于学术原因，我试图对此进行更多的了解.鉴于我有一个像这样的链表:

I realize this sort of data structure is better done with built in list type, but I'm trying to understand this more for academic reasons. Given that I have a linked list like this:

a-> b-> c-> d-> e-> f

a -> b -> c -> d -> e -> f

我想将引用更改为

b-> a-> d-> c-> f-> e

b -> a -> d -> c -> f -> e

换句话说，每对被交换.我正在使用这两个类来创建链接列表.

In other words every pair gets switched. I am using these two classes to create a linked list.

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 )，因此在列表中运行的内容(最好是一次)将与您可以做到的一样好.

Sometimes the best thing is to first think "how fast would an optimal solution be?" This seems pretty apparently O(length), so something that runs through the list, preferably once, is going to be about as good as you can do.

鉴于此，您可能会发现最简单的选择是最好的.用伪代码，它将是

Given that, you're probably going to find the simplest choice is best. In pseudocode, it would be

 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所指出的，如果完全允许使用奇数长度的列表，则需要决定如何处理奇数长度的列表.

As Matt and Jodaka note, you do need to decide what to do with an odd-length list, if an odd-length list is permitted at all.

这篇关于在Python中重新排序链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！