如何对链接列表进行排序？

Question

def listmerge(L1, L2):
    '''(CustomerNode, CustomerNode) -> CustomerNode
    Merge the linked lists headed by L1 and L2 into a single list with ticket_num in
    increasing order. Return the head of the merged list.
    REQ: Lists headed by L1 and L2 are sorted by ticket_num, all ticket_num    values are unique.
    '''

    current = L1
    while current.next != None:
        current = current.next
    current.next = L2
    return L1

客户节点的一个示例类似于LinkedList，但它是这样的：

^{pr2}$

基本上我需要优先排序。最小的数字应该是头部。在

到目前为止，我只是做了合并。在

Answer 1

我在想，在合并节点之前，你可以先按你想排序的类别排序，然后用你的listmerge(L1, L2)函数进行合并。在

假设我们有这些节点：

class Node():
    def __init__(self, name, data, next=None):
        self.name = name
        self.data = data
        self.next = next

注意：我已经将priority替换为name

现在，我将创建一个列表，其中包含所有这些节点，而不进行任何排序：

^{pr2}$

然后我可以继续按我想排序的字段进行排序。我假设按data排序：

# Helper function
def getData(node):
    return node.data

sortedList = sorted(nodeList, key=getData)

最后，通过迭代sortedList并将每个节点传递给listmerge函数来完成合并。在

要显示上述结果的示例：

# This is the list full of unordered objects. I want to sort by the data integer values
mynodelist = [Node('a', 10), Node('b', 5), Node('c', 7), Node('d', 20), Node('e', 2)]


sortedList = sorted(mynodelist, key=getData)

for o in sortedList:
    print(o.data)

### OUTPUT ###
# 2
# 5
# 7
# 10
# 20