LeetCode - 21. Merge Two Sorted Lists

문제 개요

난이도 - EASY 사용 언어 - C++

오름차순으로 정렬된 두 연결 리스트가 입력으로 들어옵니다.

단순히 두 연결 리스트를 오름차순으로 하나의 연결 리스트로 합쳐 반환하면 됩니다.

example

문제 - LeetCode - 21. Merge Two Sorted Lists

풀이

My Solutions(Github)

Solution

EASY 난이도인 만큼 크게 어려운 문제는 아닙니다.

두 연결 리스트를 순회하면서 크기가 작은 노드를 골라(오름차순으로 연결해야 하니) 새로운 연결 리스트에 연결해주면 됩니다.

ListNode* mergedHead = nullptr;
ListNode* lastNode = nullptr;

ListNode* node1 = list1;
ListNode* node2 = list2;

먼저 새로운 연결 리스트의 head 포인터인 mergedHead 포인터를 선언하고, 일종의 tail 포인터 역할을 맡는 lastNode 포인터를 선언합니다.

새로운 연결 리스트를 구성할 때는 항상 마지막에 노드를 삽입해야 하기 때문에 별도의 tail 포인터를 사용합니다.

그리고 입력된 두 연결 리스트의 순회를 위해 node1, node2 포인터를 선언하여 초기화합니다.

while (node1 && node2)
{ ... }

이제 두 리스트를 동시에 순회합니다. 두 리스트의 노드 크기를 비교해야 하기 때문에 동시에 순회해야 합니다.

만약 한쪽 리스트의 노드가 남는다면, 어차피 정렬되어 있는 리스트이기 때문에 그대로 붙이기만 하면 됩니다.

ListNode* selectedNode = nullptr;
if (node1->val < node2->val)
{
    selectedNode = node1;
    node1 = node1->next;
}
else
{
    selectedNode = node2;
    node2 = node2->next;
}

if (mergedHead == nullptr)
{
    mergedHead = selectedNode;
}
else
{
    lastNode->next = selectedNode;
}

lastNode = selectedNode;

while loop문의 내부 코드입니다.

ListNode* selectedNode = nullptr;
if (node1->val < node2->val)
{
    selectedNode = node1;
    node1 = node1->next;
}
else
{
    selectedNode = node2;
    node2 = node2->next;
}

첫 번째로는 새로운 연결 리스트에 붙일 노드를 선택합니다. 새로운 연결 리스트도 오름차순으로 정렬되어 반환되어야 하기 때문에 두 노드 중 크기가 작은 노드를 선택합니다.

if (mergedHead == nullptr)
{
    mergedHead = selectedNode;
}
else
{
    lastNode->next = selectedNode;
}

그리고 노드를 새로운 연결 리스트에 삽입합니다. 만약 새 연결 리스트의 head가 nullptr라면 첫 순회이므로 그냥 삽입하고, 아니라면 tail 노드의 next 포인터가 가리키게 합니다.

lastNode = selectedNode;

그리고 방금 삽입한 노드를 tail 포인터에 저장합니다.

제출 결과

Solution 1 result

실행 속도는 4ms가 나왔으며, 다른 C++ 제출자에 비해 95%가량의 속도가 나왔습니다.

크게 어려운 문제는 아니었기에, 다행히 충분히 만족스러운 속도가 나왔습니다.

코드 전문

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1 && !list2) return nullptr;
        
        ListNode* mergedHead = nullptr;
        ListNode* lastNode = nullptr;

        ListNode* node1 = list1;
        ListNode* node2 = list2;

        while (node1 && node2)
        {
            ListNode* selectedNode = nullptr;

            if (node1->val < node2->val)
            {
                selectedNode = node1;
                node1 = node1->next;
            }
            else
            {
                selectedNode = node2;
                node2 = node2->next;
            }

            if (mergedHead == nullptr)
            {
                mergedHead = selectedNode;
            }
            else
            {
                lastNode->next = selectedNode;
            }

            lastNode = selectedNode;
        }

        if (node1)
        {
            if (!mergedHead)
            {
                mergedHead = node1;
            }
            else
            {
                for (auto node = node1; node != nullptr; node = node->next)
                {
                    lastNode->next = node;
                    lastNode = node;
                }
            }
        }

        if (node2)
        {
            if (!mergedHead)
            {
                mergedHead = node2;
            }
            else
            {
                for (auto node = node2; node != nullptr; node = node->next)
                {
                    lastNode->next = node;
                    lastNode = node;
                }
            }
        }

        return mergedHead;   
    }
};