[Hackerrank] Merge two sorted linked lists

문제 설명

Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty.

두개의 정렬된 리스트들의 head를 가지고서, 하나의 정렬된 리스트의 head를 반환하는 문제입니다!!

제한사항

Input Format

• 2개의 head

Output Format

• SinglyLinkedListNode pointer: a reference to the head of the merged list
  (SinglyLinkedListNode의 head를 넘겨주면 됩니다.)

Others

• 중요하지 않아 보입니다!

입출력 예

• 생략

Idea

사실 문제를 보고 쉽게 풀었습니다.
하지만 다른사람의 풀이를 보고서, 공부하고 기록할겸 풀이를 남깁니다.
어렵지는 않습니다!!

Code

def mergeLists(head1, head2):
    sorted_list = SinglyLinkedList()
    shit = list()
    while head1:
        # sorted_list.insert_node(head1.data)
        shit.append(head1.data)
        # print(head1.data, end=' ')
        head1 = head1.next
    # print()
    while head2:
        # sorted_list.insert_node(head2.data)
        shit.append(head2.data)
        # print(head2.data, end=' ')
        head2 = head2.next
    shit.sort()
    for sh in shit:
        sorted_list.insert_node(sh)
    test = sorted_list.head
    while test:
        print(test.data, end=' ')
        test = test.next
    
    return sorted_list.head

Explain

각 head별로 순회(?)하면서 data들만 list에 따로 넣어줍니다.
그리고 리스트를 정렬한 후,
객체의 head를 return해야 하기에 객체에 순서대로 넣어줍니다.

다른사람의 풀이

def mergeLists(head1, head2):
    if not head1 and not head2:
        return head1
    if not head1:
        return head2
    if not head2:
        return head1
    merged_list = SinglyLinkedListNode(None)
    c = merged_list
    c1 = head1
    c2 = head2
    while c1 and c2:
        print(merged_list)
        if c1.data <= c2.data:
            c.next = c1
            c1 = c1.next
        else:
            c.next = c2
            c2 = c2.next
        c = c.next
    if c1:
        c.next = c1
    if c2:
        c.next = c2
    return merged_list.next

감히 평가하자면 파이썬스럽지 않은 코드이지만, 그럼에도 잘 짯습니다. 위의 코드를 조금 수정하자면 아래와 같이 나타낼 수 있을것 같습니다.

def mergeLists(head1, head2):
    merged_list = SinglyLinkedList()
    
    while head1 or head2:
        if not head1:
            merged_list.insert_node(head2.data)
            head2 = head2.next
        elif not head2:
            merged_list.insert_node(head1.data)
            head1 = head1.next
        elif head1.data < head2.data:
            merged_list.insert_node(head1.data)
            head1 = head1.next
        else:
            merged_list.insert_node(head2.data)
            head2 = head2.next
    return merged_list.head