[Easy] Leetcode | 21. Merge Two Sorted Lists | Linked list

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

- 문제
연결 리스트를 이용하여 주어진 정렬된 두 리스트를 병합시켜 새 리스트를 만들어 반환하는 문제이다.
노드 구조체는 문제에 주어진다.

- 풀이
우선 주어진 리스트가 NULL일 경우는 나머지 리스트를 그대로 반환해준다.
l1과 l2를 가리키는 리스트를 first, second로 선언한다. head라는 더미노드를 만들고 head->next에 반환할 리스트의 첫 노드를 생성한다. 즉 병합된 리스트의 첫 노드는 head->next 노드이다. curNode를 생성해 새로 노드가 추가될 곳을 가리키도록 한다. tempList는 루프를 진행하며 l1과 l2중 크기가 작은 노드를 가리키도록 하며 curNode->next에 tempList->val을 val로 갖는 노드를 생성한다.첫 루프는 둘 중 하나의 리스트가 모두 추가되면 종료되며 두번째 루프에서 나머지 노드들을 차례로 추가한다.
루프를 개별로 두번 반복하므로 시간 복잡도는 O(n+m) = O(n)이 될 것이고 공간 복잡도는 반환하는 리스트가 가지는 노드 개수 O(n+m) = O(n)이 될 것이다. 다음은 풀이 코드이다.  

/*
 	* Definition for singly-linked list.
 	* struct ListNode {
 	*     int val;
 	*     ListNode *next;
 	*     ListNode(int x) : val(x), next(NULL) {}
 	* };
 */
class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(l1 == NULL && l2 == NULL)
            return NULL;
        else if(l1 == NULL)
            return l2;
        else if(l2 == NULL)
            return l1;
        
        ListNode* firstList  = l1;
        ListNode* secondList = l2;
        ListNode* head = new ListNode(0);
        ListNode* curNode = head;
        ListNode* tempList;
        
        bool bFirst = true;
        while(firstList != NULL && secondList != NULL)
        {
            // val이 작은 노드를 고른다.
            tempList = (firstList->val > secondList->val) ? secondList : firstList;
            bFirst = (tempList == firstList) ? true : false;
            
            // 현재 노드의 다음 노드에 추가 한다.
            curNode->next = new ListNode(tempList->val);
            curNode = curNode->next;
            
            if(bFirst)
                firstList = firstList->next;
            else
                secondList = secondList->next;
        }
        
        tempList = (firstList == NULL) ? secondList : firstList;
        while(tempList != NULL) {
            curNode->next = new ListNode(tempList->val);
            curNode = curNode->next;
            tempList = tempList->next;
        }
        
        return head->next;
    }
};

사실 매개 변수로 들어오는 두 리스트는 해당 함수를 통해 수정되어선 안된다고 생각해 l1, l2를 그대로 반환하면 안될 것 같았지만 const가 없어 둘 중 하나가 NULL일 경우엔 그냥 그대로 반환했다.