リンクされたリストをどのように並べ替えるのですか？顧客ノードの

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のようなものである：

list1 = CustomerNode(priority, data, next = None) 

基本的に私は、ソート優先順位を罠。最も低い数字が頭でなければなりません。

これまでのところ、私はちょうどマージしました。

Answer 1

あなたのノードをマージする前に、並べ替えたいカテゴリで並べ替えてから、listmerge(L1, L2)関数を使ってマージすることができます。

我々はこれらのノードを持っているとしましょう：

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

注：私は今、私が行っ任意の並べ替えなしに、これらすべてのノードを保持しているリストを作成するつもりですname

でpriorityを交換しました：

nodeList = [<__main__.Node object at 0x1021e7320>, <__main__.Node object at 0x1021e7278>, <__main__.Node object at 0x1021e72b0>, <__main__.Node object at 0x1021e7240>, <__main__.Node object at 0x1021e72e8>] 

次に、並べ替えたいフィールドで並べ替えることができます。私は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