[LeetCode] 21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

두 개의 정렬된 리스트를 받아, 정렬된 머지 리스트로 반환하는 문제이다.

 

처음 두 개의 생각이 들었다.

1. 일단 합치고 정렬한다.

2. node를 받으며 정렬 순서대로 넣는다.

 

1번의 경우에는 O(nlogn)의 정렬을 쓰면 될 것 같긴 했지만 2번으로 풀기로 생각했다. C++에서는 기본적으로 Linked-List로 주어졌기 때문이다.

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* result; // result list
        ListNode* temp; // current node
        /*---input null check---*/
        if(l1==nullptr&&l2==nullptr)
            return result;
        else if(l1==nullptr)
            return l2;
        else if(l2==nullptr)
            return l1;
        
        /*---initialize---*/
        if(l1->val <= l2->val) {
            result = new ListNode(l1->val);
            temp=result;
            l1=l1->next;
        }
        else {
            result = new ListNode(l2->val);
            temp=result;
            l2=l2->next;
        }
        
        while(l1!=nullptr||l2!=nullptr) {
            if(l1==nullptr && l2!=nullptr) {
                temp->next = new ListNode(l2->val);
                l2=l2->next;
                temp=temp->next;
                continue;
            }
            if(l2==nullptr && l1!=nullptr) {
                temp->next = new ListNode(l1->val);
                l1=l1->next;
                temp=temp->next;
                continue;
            }
            if(l1->val <= l2->val) {
                temp->next = new ListNode(l1->val);
                l1=l1->next;
            }
            else {
                temp->next = new ListNode(l2->val);
                l2=l2->next;
            }
            temp=temp->next;
        }
        return result;
    }
};

 

간만에 C++을 사용해서 링크드 리스트에서 포인터의 사용법에서 살짝 혼돈이 왔던 점을 제외하면 스무스하게 풀이에 성공했다.

 

input이 빈 리스트일 경우에 런타임 에러가 나서 잡아 주었다. 틀린 TC의 input을 알려주는 점에서 BOJ보다 틀린 점을 찾기 쉬웠다. 좋은 점인 것 같다.