Merge Two Sorted List

problem

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

두개의 정렬된 linked_list를 받아서 합치는 것이 목표입니다.

solution

/**
 * 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* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        
        ListNode * current;
        ListNode * answer;
        
        if(l1->val <= l2->val){
            current = l1;
            l1 = l1->next;
        }
        else{
            current = l2;
            l2 = l2->next;
        }
        answer = current;
        
        while(l1 != nullptr && l2 != nullptr)
        {
            if(l1->val <= l2->val)
            {
                current->next = l1;
                l1 = l1->next;
                current = current->next;
            }
            else
            {
                current->next = l2;
                l2 = l2->next;
                current = current->next;
            }
        }
        if(l1 != nullptr){
            current->next = l1;
        }
        else if(l2 != nullptr)
        {
            current->next = l2;
        }
        return answer;
    }
};

후기

처음에는 list_node를 처음부터 끝까지 다 만들어서 써서 성능이 좋게 나오지 못했는데, 생각해보니까 새로 list_node를 만들필요가 없고 l1과 l2의 link를 다시 연결해면 해결되는 문제였습니다. 또 L1, L2가 while문을 끝내고 나면 나머지 꼬리 부분을 가지고 있으니까 바로 연결하면 쉽게 해결할 수 있는 문제였습니다.

알고리즘을 풀고 다른 사람들이 구현한 것을 보니까 재귀 함수로 풀 수 있는 문제라는 것을 알게 되었습니다. 코드도 깔끔하고 더 직관적이라 재귀가 더 좋은 것 같습니다.