[Hackerrank] Merge two sorted linked lists

문제 설명

두 개의 정렬된 단일 연결 리스트 병합

두 개의 정렬된 단일 연결 리스트의 헤드 포인터가 주어졌을 때, 이를 하나의 정렬된 단일 연결 리스트로 병합하세요. 어느 한쪽 리스트의 헤드 포인터는 null일 수 있습니다.

---

함수 설명

mergeLists 함수를 완성하세요. 함수는 다음과 같은 매개변수를 받습니다:

• SinglyLinkedListNode pointer headA: 첫 번째 연결 리스트의 헤드 포인터
• SinglyLinkedListNode pointer headB: 두 번째 연결 리스트의 헤드 포인터

반환값:

• SinglyLinkedListNode pointer: 병합된 리스트의 헤드 포인터

---

입력 형식

첫 번째 줄에는 테스트 케이스의 개수 ttt가 주어집니다.

각 테스트 케이스는 다음과 같은 형식으로 이루어져 있습니다:

1. 첫 번째 줄에는 첫 번째 연결 리스트의 길이 n이 주어집니다.
2. 다음 n개의 줄에는 첫 번째 연결 리스트의 각 요소가 주어집니다.
3. 그다음 줄에는 두 번째 연결 리스트의 길이 m이 주어집니다.
4. 다음 m개의 줄에는 두 번째 연결 리스트의 각 요소가 주어집니다.

---

제약 조건

• 1≤t≤10
• 1≤n, m≤1000
• 1≤list[i]≤1000 (여기서 list[i]는 리스트의 i-번째 요소를 의미)

---

출력 형식

각 테스트 케이스에 대해 병합된 리스트의 요소들을 공백으로 구분하여 출력합니다.

---

예제 입력

 

1 3 1 3 7 2 1 2

예제 출력

 

1 1 2 3 7

 

 

지난번 문제들과 비슷한 자료구조 문제이다. 이번 문제는 2개의 single linked list를 크기 순서대로 하나로 합치는 문제이다.

이 문제를 해결하기 위해 먼저 tmp라는 새로운 single linked list를 만들었다. 그리고 head1과 head2의 data를 비교해서 먼저 더 작은 값을 가지는 노드를 tmp의 head로 넣어주었다. 그리고 포인터를 다음 노드로 이동해 주었다. 그 후 반복문을 이용해서 head1과 head2가 None이 될 떄까지 2개의 data중 더 작은 데이터를 하나씩 tmp에 넣어주면서 포인터를 다음 노드로 이동해주었다. 그러면 head1과 head2중 하나는 리스트의 끝에 도달해서 none이 되고, 남은 노드들은 이미 정리가 되어 있으니 남은 노드들을 tmp에 연결해 주면 코드가 완성이 된다.

완성된 코드는 다음과 같다.

def mergeLists(head1, head2):
    tmp = SinglyLinkedList()
    if head1.data < head2.data:
        llist = SinglyLinkedListNode(head1.data)
        tmp.head = llist
        head1 = head1.next
    else:
        llist = SinglyLinkedListNode(head2.data)
        tmp.head = llist
        head2 = head2.next
    while head1 is not None and head2 is not None:
        if head1.data < head2.data:
            llist.next = head1
            llist = llist.next
            head1 = head1.next
        else:
            llist.next = head2
            llist = llist.next
            head2 = head2.next
    if head1 is not None:
        llist.next = head1
    if head2 is not None:
        llist.next = head2   
    return tmp.head