[LeetCode] 21. Merge Two Sorted Lists c++

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

주어진 두 개의 노드를 오름차순으로 합치는 문제입니다.

 

문제 해결

RECURSIVE APPROACH

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(NULL == list1){
            return list2;
        }
        if(NULL == list2){
            return list1;
        }
        if(list1->val <= list2->val){
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else{
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

 

ITERATIVE APPROACH

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL){
            return list2;
        }
        if(list2 == NULL){
            return list1;
        }
        ListNode *ptr = list1;
        if(list1->val > list2->val){
            ptr = list2;
            list2 = list2->next;
        }
        else{
            list1 = list1->next;
        }
        
        ListNode *curr = ptr;
        while(list1 && list2){
            if(list1->val < list2->val){
                curr->next = list1;
                list1 = list1->next;
            }
            else{
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
        if(!list1){
            curr->next = list2;
        }
        else{
            curr->next = list1;
        }
        return ptr;
    }
};