[해커랭크] Merge two sorted linked lists (C++)

문제 링크: www.hackerrank.com/challenges/merge-two-sorted-linked-lists/problem?h_r=internal-search

Merge two sorted linked lists | HackerRank

1. 주의할 점

- 한쪽의 List가 먼저 끝나는 경우, 이에 대한 처리를 명확히 한다

 

2. 구현

- 2개의 List를 합할 SinglyLinkedList li를 생성한다

- 2개의 List가 모두 NULL을 가리키지 않는다면, 다음과 같은 작업을 반복한다

- 첫 째, head1이 NULL을 가리킨다면 남은 head2의 데이터들을 li에 추가한다

- 둘 째, head2이 NULL을 가리킨다면 남은 head1의 데이터들을 li에 추가한다

- 마지막으로, 둘다 NULL을 가리키지 않는다면 2개의 값을 비교하여 작은 값을 li에 추가하고 추가된 값이 속한 list는 다음 Node를 가리키도록 설정한다

SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedList* li = new SinglyLinkedList();
    while(head1 || head2){
        if(head1==nullptr){
            while(head2){
                li->insert_node(head2->data);
                head2 = head2->next;
            }
        }
        else if(head2==nullptr){
            while(head1){
                li->insert_node(head1->data);
                head1 = head1->next;
            }
        }
        else{
            int h1 = head1->data;
            int h2 = head2->data;
            if(h1<=h2){
                li->insert_node(h1);
                head1 = head1->next;
            }
            else{
                li->insert_node(h2);
                head2 = head2->next;
            }
        }
    }
    return li->head;
}