Merge Two Sorted Lists

괜히 오기가 생겨서 처음 떠오른 아이디어로 풀다가 머리가 쪼개질 뻔하였다. STL은 쉬운데...막상 구조체로 직접 구현하려니 어려웠다.

1. 그냥 두 개 합친다음에, 버블정렬 같은거로 해도 될거 같다. 포인터 저장하는게 귀찮겠지만...

2. 나는 우선 head를 하나 만들고, 두 리스트에 따로 각자 Cur 포인터를 만들어서 head에서 다음 연결을 위해 두 리스트를 참조할 때, 각자의 Cur포인터를 타고 따라가 val을 찾고 선택한 node를 head->next 해준뒤, 해당 Cur는 전진시켜주었다. 8ms, 14.9MB. 73%보다 빠르다고 하니 맘에 든다.

head = l1 or l2를 해서 원본이 훼손되는 것이 싫다면, head선언에서 null이 아닌 new ListNode()를 하면 된다. 다들 비슷하게 푼거 봐서는 분기를 어떻게 짜느냐에 따라 아주 약간의 시간 차이가 나는듯.

이해는 직접 VS 디버깅 모드에서 한 줄씩 실행을 하면 잘 될듯 싶다. (VS는 신이다. 나는 천민이고 ㅠ)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        ListNode* head = nullptr, *cur;
        ListNode* l1Cur=l1;
        ListNode* l2Cur=l2;
        
        if (l1->val < l2->val)
        {
            head = l1;
            l1Cur = l1Cur->next;
        }
        else
        {
            head = l2;
            l2Cur = l2Cur->next;
        }

        cur = head;

        while (true)
        {
            //nullptr체크
            if (l1Cur == nullptr && l2Cur == nullptr)
            {
                break;
            }

            //어느쪽을 이을지 체크
            if (l1Cur == nullptr)
            {
                cur->next = l2Cur;
                break;
            }
            if (l2Cur == nullptr)
            {
                cur->next = l1Cur;
                break;
            }
            if (l1Cur->val < l2Cur->val)
            {
                cur->next = l1Cur;
                l1Cur = l1Cur->next;
                cur = cur->next;
            }
            else
            {
                cur->next = l2Cur;
                l2Cur = l2Cur->next;
                cur = cur->next;
            }
        }


        return head;
    }
};