[C++] LeetCode - Merge Two Sorted Lists

이번에는 merge two sorted lists를 풀어봤습니다. 역시나 쉬운 예제이며, linked list가 2개가 주어지고, 작은 순서대로 차례차례 새로운 링키드 리스트를 만드는게 목표입니다.

---

문제 정의

---

접근 방법

• 두 리스트 중 하나라도 nullptr가 아니라면, 계속 while loop 이 돌아갑니다. 차례차례 next를 써가면서 원소의 값을 비교하고, 작은 것을 선택한 뒤 정답 리스트에 추가합니다. 단순합니다.
• 만약 두 리스트 중 하나가 nullptr인지도 체크해서 메모리 에러가 발생하지 않도록 주의합니다.

---

결과

확실히 쉬운 문제는 고수들이 없는건지, 답이 한정적인건지 생각보다 런타임이 빠르게 나옵니다. 메모리 사용은... 자료구조에 대해 좀 더 이해가 필요한 것 같아요.

• Runtime: 8 ms, faster than 69.55% of C++ online submissions for Merge Two Sorted Lists.
• Memory Usage: 14.9 MB, less than 15.61% of C++ online submissions for Merge Two Sorted Lists.

---

코드

---

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        ListNode* ch = new ListNode(0);
        ListNode* answer = ch;
 
        
        
        while (list1 != nullptr || list2 != nullptr) {
            
            if (list1 == nullptr) {
                // only list 2 can be added
                answer->next = new ListNode(list2->val);
                answer = answer->next;
                list2 = list2->next;
                
               
            } else if (list2 == nullptr) {
                // only list 1 can be added
                answer->next = new ListNode(list1->val);
                answer = answer->next;
                list1 = list1->next;
                
            } else {
                // both lists are not nullptr
                if (list1->val <= list2->val) {
                    answer->next = new ListNode(list1->val);
                    answer = answer->next;
                    list1 = list1->next;
              } else {
                    answer->next = new ListNode(list2->val);
                    answer = answer->next;
                    list2 = list2->next;
              }
            }
        }
        
        
        return ch->next;
    }
};

---