[Leetcode][C++][난이도 Easy] Merge Two Sorted Lists

Leetcode의 난이도 easy 6번째 문제는 merge two sorted lists라는 문제입니다. 이미 정렬된 2개의 list를 합치고 반환하는 대신, 합쳐진 list는 또 정렬된 상태로 변환되어야 합니다. 그리고 반환되는 정보는 합쳐진 list의 head 포인터입니다. 우선 예제와 함께 문제에 대한 설명을 이어가겠습니다. 

 

 

Merge Two Sorted Lists 문제 분석 

 

[사진 1] Merge Two Sorted Lists 문제

 

위 [사진 1]의 첫번째 예제부터 살펴보겠습니다. 첫번째 list는 붉은색으로 표시되어 있습니다. 이 때 head가 1이고, 차례대로 값이 2, 4인 노드를 가리키고 있습니다. 두번째 list는 보라색으로 표시되어 있습니다. 이 때 head가 1이고, 차례대로 값이 3, 4인 노드를 가리키고 있습니다. 이제 문제에서 제시한 조건대로, 두 list를 합칠 때 정렬된 상태로 합쳐보면, 바로 아래의 세번째 list가 됩니다. 우선 두 list 모두 값이 1, 4인 노드가 존재하는데요, 이 두 노드의 순서는 상관없습니다. 핵심은, 첫번째 list의 값이 2인 노드가, 두번째 list의 값이 3인 노드 앞에 항상 위치해야 합니다. 참고로 오름차순으로 정렬되어야 합니다. 따라서, 세번째 list는 1, 2, 2, 3, 4, 4로 정렬되어야 합니다. 

 

두번째 예제를 살펴보겠습니다. 두번째 예제는 정말 간단한데요, 두 list 모두 아무 정보도 없이 head가 null 포인터로 지정된 경우입니다. 이 경우에 두 list를 합쳐도 결국 null 포인터만 가리키는 head만 있으면 됩니다. 그러면 세번째 예제는 어떨까요? 이 경우에 첫번째 list는 head가 null 포인터로 지정되어 있어서, 아무런 정보도 없는 list입니다. 하지만 두번째 list는 값이 0인 노드 1개만 존재합니다. 이 경우도 역시 간단합니다. 왜냐하면 두 list를 합쳤을 때 두번째 list만 존재하기 때문이죠. 만약 코드로 구현한다면, 둘 중 하나의 list가 null 포인터이고, 다른 list는 값이 있는 노드가 존재한다면, 노드가 존재하는 list를 바로 반환하면 되니까요. 

 

 

Merge Two Sorted Lists 문제 해결을 위한 C++ 코드

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
#include <map>

void append(ListNode** head_ref, int new_data) 
{ 
    ListNode* new_node = new ListNode();
    ListNode *last = *head_ref; 
    new_node->val = new_data; 
    new_node->next = NULL; 

    if (*head_ref == NULL) 
    { 
        *head_ref = new_node; 
        return; 
    } 
  
    while (last->next != NULL) 
        last = last->next; 
  
    last->next = new_node; 
    return; 
} 


class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        map<int, int, less<int>> temp_map;
        ListNode *result;
        
        if (list1 == NULL && list2 == NULL)
            return NULL;
        else if (list1 == NULL && list2 != NULL)
            return list2;
        else if (list1 != NULL && list2 == NULL)
            return list1;
        else
        {
            ListNode* temp_list = list1;
            while (temp_list)
            {
                temp_map[temp_list->val]++;
                temp_list = temp_list->next;
            }
            temp_list = list2;
            while (temp_list)
            {
                temp_map[temp_list->val]++;
                temp_list = temp_list->next;
            }
            
            result = NULL;
            
            for (auto &it : temp_map)
            {
                for(int i = 0; i < it.second; i++)
                {
                    append(&result, it.first);
                }
            }
            
            return result;
        }
    }
};

 

그러면 바로 제가 작성한 코드를 살펴보겠습니다. 저는 먼저 null만 있는 list를 선별하는 조건문을 먼저 나열했습니다. 첫번째 조건문에서는 두 list가 모두 null인 경우입니다. 이때는 당연히 합쳐도 null만 있으므로, null을 반환합니다. 두번째 조건문에서는 첫번째 list만 null인 경우입니다. 이 경우는 두번째 list만 반환하면 됩니다. 세번째 조건문에서는 두번째 list만 null인 경우입니다. 이 경우에는 첫번째 list만 반환하면 됩니다. 그러면 이에 해당 안되는 경우는 두 list 모두 값이 존재하는 경우입니다. 이 경우에 대해서도 살펴보겠습니다. 

 

우선 temp_map이라는 map 변수를 사용해서, 두 list에 저장되어 있는 값들을 순차적으로 temp_map에 저장합니다. temp_map을 선언할 때, <int, int, less<int>>에 less<int>라는 부분이 있습니다. 이 부분은 map에 저장되는 key를 오름차순으로 정렬하는 역할을 합니다. 자세한 설명은 맨 아래 <참고 자료>에 링크를 올려두었습니다. 그리고 각 list에서 중복되는 값이 발생하면, map에 저장되는 key의 value를 1씩 증가시킵니다. 이는 나중에 최종 list를 생성할 때, 중복되는 값들도 최종 list에 삽입되어야 하므로 필요한 작업이라고 생각했습니다. 이렇게 생성된 temp_map 변수에 대해서 다시 loop을 실행해서, 함수 append를 호출합니다. 함수 append는 linked list를 생성하는 함수와 동일합니다. 

 

 

Merge Two Sorted Lists 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

[사진 2] Merge Two Sorted Lists 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

이제 다른 사람이 작성한 코드도 살펴볼까요? 이 분은 recussive와 iterative, 두가지 코드를 모두 올려두셨지만, iterative 코드만 살펴보도록 하겠습니다. 이 코드는 저처럼 map을 따로 두지 않았습니다. 그대신 포인터 변수 ptr 하나에다가 첫번째와 두번째 list에 저장된 값을 서로 비교하면서 다음 노드를 가리키는 next만 갱신시키는 방향으로 구현했습니다. 그리고 처음에 둘 중 하나의 list만 null인 경우만을 체크했네요. 구지 map을 따로 두지 않고, 포인터 변수 하나로 문제를 해결하는 이 분의 코드가 더 좋아보입니다. 역시 갈 길이 멉니다.

 

 

[참고 자료]

 

1. map 관련 설명 

 

 

지금까지 leetcode easy 난이도 문제 중 하나였던 merge two sorted lists 문제를 살펴보았습니다. 다음 문제도 이어서 포스트 하겠습니다!