[ leetcode 문제풀이 ] Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

Merge Two Sorted Lists - LeetCode

(Merge Two Sorted Lists 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Merge Two Sorted Lists 문제 설명 >

 

Merge Two Sorted Lists 문제는 다음과 같다.

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

정렬된 두 개의 linked lists의 heads인 list1, list2가 주어진다.

두 lists를 하나의 sorted list로 합쳐라. 합쳐진 list는 두 lists의 nodes를 결합해 만들어져야 한다.

 

합쳐진 linked list의 head를 리턴하여라.

 

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한조건은 다음과 같다:

두 lists의 노드 수는 [0, 50] 범위 내에 있다.

-100 ≤ Node.val ≤ 100

list1과 list2는 모두 단조증가하는 순으로 정렬되어 있다.

 

 

 

---

< Merge Two Sorted Lists 문제 접근(1) >

 

먼저 iteration 방식으로 알고리즘을 구성하였다. (Cpp 사용)

 

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(list1 == nullptr) return list2;
    if(list2 == nullptr || list1->val > list2->val)
        return mergeTwoLists(list2, list1);
        
    ListNode *head = list1, *tail = list1;
    list1 = list1->next;
    while(list1 != nullptr && list2 != nullptr){
        if(list1->val > list2->val){
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
        else{
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
    }
    if(list1 == nullptr) tail->next = list2;
    else tail->next = list1;
       
    return head;
} // runtime : 7 ms (faster than 83.67 %), memory usage : 14.7 MB (less than 82.99 %)

 

list1의 head가 무조건 merge된 list의 시작이 되도록 강제. list1→val == list2→val이라면 list1이 먼저 이어지도록 설정.

 

head는 merged list의 시작, tail은 merged list의 끝(while loop를 통해 계속 업데이트 됨) list1, list2는 아직 merge 하지 않은 list1과 list2의 시작을 나타냄.

 

while loop조건 : list1과 list2 중 어느 하나가 다 merge될때까지 list1→val과 list2→val을 비교해 더 작은(작거나 같은) 값을 지닌 ListNode를 tail의 다음 노드로 연결. tail은 연결한 노드로 이동. list도 이에 따라 1칸 이동.

 

while loop를 통과하면 아직 연결되지 않은 list1 or list2의 부분을 tail과 연결해줌.

 

 

 

---

< Merge Two Sorted Lists 문제 접근(2) >

 

recursion 방식으로도 코드를 작성하였다. (Cpp 사용)

 

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(list1 == nullptr) return list2;
    if(list2 == nullptr)
        return mergeTwoLists(list2, list1);
        
    if(list1->val <= list2->val){
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
} // runtime : 8 ms (faster than 77.61 %), memory usage : 14.8 MB (less than 83.02 %)

 

확실히 recursion을 사용하는 방식이 간단한것 같다. 다만 부분 문제를 떠올리려 할 때 머리가 꼬여서 잘 활용을 못하는 중이다,,