[ leetcode ] 21. Merge Two Sorted Lists

주어진 두 오름 차순으로 정렬된 linked list를 하나의 오름차순으로 정렬된 linked list로 합쳐서 반환하는 문제입니다. 기존 제공된 두 linked list의 node를 그대로 사용해야 하는 문제입니다.

해당 문제는 반복문으로도 해결할 수 있고, 같은 문제가 두 노드에 대해 반복되므로 재귀적으로도 해결할 수 있습니다.

 

먼저, 두 linked list의 노드 각각을 비교하여 a, b 리스트 중 b리스트의 현재 노드가 더 크다면 a 리스트에서 b 리스트 노드보다 더 큰 값이 나올 때 까지 노드를 지나가며 지나온 노드들을 b리스트 노드 앞에 배치시켜야 합니다.

반복문으로 해결한다면 다음과 같습니다.

while (one != NULL && two != NULL) {
    if (one->val <= two->val) {
        while (one->next && one->next->val <= two->val) one = one->next;
        ListNode* temp = one;
        one = one->next;
        temp->next = two;
    }
    else {
        while (two->next && two->next->val < one->val) two = two->next;
        ListNode* temp = two;
        two = two->next;
        temp->next = one;
    }
}

리스트의 두 노드를 비교하여 이어 주고, 나머지 리스트들에서 두 노드를 비교하는 방식이 같으므로 재귀적인 방식으로 해결할 수 있습니다.

if (one->val <= two->val) {
    one->next = mergeTwoLists(one->next, two);
    return one;
}
else {
    two->next = mergeTwoLists(one, two->next);
    return two;
}

전체 코드는 아래와 같습니다.

/**
 * 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* one = list1;
        ListNode* two = list2;
        if (one == NULL || two == NULL)
            return one ? one : two;
        
        ListNode* head = one->val <= two->val ? one : two;
        if (one->val <= two->val) {
            one->next = mergeTwoLists(one->next, two);
            return one;
        }
        else {
            two->next = mergeTwoLists(one, two->next);
            return two;
        }
        // while (one != NULL && two != NULL) {
        //     if (one->val <= two->val) {
        //         while (one->next && one->next->val <= two->val) one = one->next;
        //         ListNode* temp = one;
        //         one = one->next;
        //         temp->next = two;
        //     }
        //     else {
        //         while (two->next && two->next->val < one->val) two = two->next;
        //         ListNode* temp = two;
        //         two = two->next;
        //         temp->next = one;
        //     }
        // }
        return head;
    }
};