문제 푼 날짜 : 2021-11-24

문제

문제 링크 : https://leetcode.com/problems/merge-two-sorted-lists/

접근 및 풀이

MergeSort를 구현할 때와 동일한 로직으로 구현해주었다.

1. 정렬된 값들을 저장해주기 위해 새로운 ListNode(list3)를 선언해준다.
2. list1, list2 가 모두 nullptr이 아닐 때까지 순회해준다.
   2-1. list1, list2의 현재 값들을 비교해서 값이 더 작은 쪽을 list3의 next값으로 이어준다.
3. 순회가 끝나면, list1과 list2에 남아있는 값들을 list3에 이어준다.
4. head는 Dummy Node 이므로 head->next를 return 해준다.

코드

/**
 * 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* list3 = new ListNode();
        ListNode* head = list3; // Dummy Node
        
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                list3->next = list1;
                list1 = list1->next;
            } else {
                list3->next = list2;
                list2 = list2->next;
            }
            list3 = list3->next;
        }
        if (list1 != nullptr) {
            list3->next = list1;
        } else if (list2 != nullptr) {
            list3->next = list2;
        }
        return head->next;
    }
};

결과

피드백

구조체나 클래스에 포인터가 붙어있으면 쫄고 들어가는 버릇을 고쳐야겠다.
이와 관련된 것을 이용하여 해결하는 문제를 좀 더 많이 풀어봐서 익숙해져야 될 것 같다.