LeetCode : 21. Merge Two Sorted Lists

LeetCode에서 전에 이런 문제를 풀었던 기억이?...

Merge Sort을 할때에 두 개로 나눈 배열을 합병하는 과정을 그대로 구현하면 된다.

 

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // int idx = 0;
        ListNode* dummy = new ListNode();
        ListNode* curr = dummy;
        if(l1==NULL || l2==NULL){
            if(l1==NULL){
                return l2;
            }else{
                return l1;
            }
        }
        
        while(l1!=NULL || l2!=NULL){
            if(l1!=NULL && l2!=NULL){
                if((l1->val)<(l2->val)){
                    curr->val = l1->val;
                    l1 = l1->next;
                }else{
                    curr->val = l2->val;
                    l2 = l2->next;
                }                
            }else{
                if(l1!=NULL){
                    curr->val = l1->val;
                    l1 = l1->next;
                }else{
                    curr->val = l2->val;
                    l2 = l2->next;
                }
            }
 
            if(l1==NULL && l2==NULL){
                break;
            }
            
            curr->next = new ListNode();
            curr = curr->next;
        }
        
        return dummy;
    }
};