개요

[HackerRank]MergeTwoSortedLinkedList

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.

접근 방식

첫번째 시도(맞음)

수열의 길이도 어차피 1000밖에 안 되서 가장 naive하게 시도를 했다.
벡터 하나를 선언한 후, 두 연결리스트의 원소 값을 다 저장 후 sorting을 해줬다.
그 후 새 연결리스트를 선언한 후, sorting된 값들을 다 저장해 연결리스트를 반환해줬다.

두번째 시도(맞음)

첫번째 시도를 거의 다 구현중 생각이 난 방법이라 일단 첫번째시도를 완료하고 시도해봤다.
연결리스트 ret을 하나 생성해준 후, 매 차례마다 head1과 head2의 맨 앞 값을 비교해서
더 작은 값을 ret에 연결해주는 것을 반복하면 된다.
그러다 한 연결리스트가 끝에 다다르면 나머지 연결리스트의 남은 값들을 다 연결해주면 끝

첫번째 코드(맞음)

// Complete the mergeLists function below.

/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode* next;
 * };
 *
 */
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
	//checking Either container empty 
    if(head1 == nullptr && head2 == nullptr){
        return nullptr;
    } 
    else if(head1 ==nullptr){
        return head2;
    }
    else if(head2 == nullptr){
        return head1;
    }
    
    //merge two container
    vector<int> v;
    SinglyLinkedListNode* tmp=head1;
    while(tmp != nullptr){
        v.push_back(tmp->data);
        tmp=tmp->next;
    }
    tmp=head2;
    while(tmp!=nullptr){
        v.push_back(tmp->data);
        tmp=tmp->next;
    }
    sort(v.begin(),v.end());
    
    //make new linked list and return
    SinglyLinkedListNode* prev=nullptr;
    SinglyLinkedListNode* head=nullptr;
    for(int i=0;i<v.size();i++){
        SinglyLinkedListNode* cur=new SinglyLinkedListNode(v[i]);
        if(i==0) {
            head=cur;
            prev=cur;
            continue;
        }
        prev->next=cur;
        prev=cur;
    }
    return head;
}

두번째 방법 코드(맞음)

// Complete the mergeLists function below.

/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode* next;
 * };
 *
 */
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {

//checking Eiter container EMpty 
    if(head1 == nullptr && head2 == nullptr){
        return nullptr;
    } 
    else if(head1 ==nullptr){
        return head2;
    }
    else if(head2 == nullptr){
        return head1;
    }
    
//compare head1,head2 's head value, and link smaller value into rethead
    SinglyLinkedListNode *retHead;
    SinglyLinkedListNode *retIter;
    
    SinglyLinkedListNode* iter1 = head1;
    SinglyLinkedListNode* iter2 = head2;
    
    if(iter1->data >=iter2->data){
        retHead=iter2;
        iter2=iter2->next;
    }
    else{
        retHead=iter1;
        iter1=iter1->next;
    }
    retIter=retHead;
    while(iter1!=nullptr && iter2!=nullptr){
        if(iter1->data >= iter2->data){
            retIter->next=iter2;
            retIter=iter2;
            iter2=iter2->next;
        }
        else{
            retIter->next=iter1;
            retIter=iter1;
            iter1=iter1->next;
        }
    }
    
//if one list run out, link entire other list into rethead
    if(iter1 == nullptr && iter2==nullptr){
       return retHead; 
    }
    else if(iter1==nullptr){
        while(iter2!=nullptr){
            retIter->next=iter2;
            retIter=iter2;
            iter2=iter2->next;
        }
    }
    else {
        while(iter1!=nullptr){
            retIter->next=iter1;
            retIter=iter1;
            iter1=iter1->next;
        }
    }
    return retHead;
}