연결된 목록을 어떻게 정렬합니까?

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