Merge Two Sorted Lists

Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode

 

내가 한 것

/**
 * 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 *head;
    
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        // empty array
        if (!list1 && !list2 || list1 && !list2) {
            return list1;
        }
        else if (!list1 && list2) {
            return list2;
        } else { // if (list1 && list2) // not empty
            
            ListNode *node1 = list1;
            ListNode *node2 = list2; 
            int node1Idx = 0;
            int node2Idx = 0;
            
            while (node1 && node2) {
                // list1 기준으로 하자
                if (node1->val <= node2->val) {
                    // node2 의 값이 더 크거나 같다.
                    // 그 다음것과 비교
                    while (node1->val <= node2->val) {
                        node1 = node1->next;
                        node1Idx++;
                        if (!node1)
                            break;
                    }
                    // 만약 이제 작으면 앞쪽에 넣고
                    
                    list1 = addAtIndex(list1, node1Idx, node2->val);
                    node1Idx++;
                    node2Idx++;
                    node2 = node2->next;
                } else if (node1->val > node2->val) {
                    // node1 첫번째와 node2 첫번째를 비교해서 node2 더 작으면 node1 첫번째이전에 넣고,
                    
                    list1 = addAtIndex(list1, node1Idx, node2->val);
                    node1Idx++;
                    node2Idx++;
                    node2 = node2->next;
                }
            }
            
            
            if (node2) {
                while(node2) {
                    addAtIndex(list1, node1Idx, node2->val);
                    node2 = node2->next;
                    node1Idx++;
                }
            }
            
            return list1;
        } 
    }
    
    ListNode* addAtIndex(ListNode* headNode, int index, int val) {
        
        ListNode *node = headNode;
        ListNode *listNode = new ListNode();
        listNode->val = val;
        
        if (index == 0) {
            if (!node) 
                headNode = listNode;
            else {
                listNode->next = headNode;
                headNode = listNode;
            }
            
        } else {
            int i = 0;
            while(i < index - 1) {
                node = node->next;
                i++;
            }
            
            listNode->next = node->next;
            node->next = listNode;
            
        }
        
        head = headNode;
        return head;
    }
    
};

베스트

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       if(!l1)
           return l2;
        
        if(!l2)
            return l1;
        
        if(l1->val<=l2->val){
            l1->next=mergeTwoLists(l1->next,l2);
            return l1;
        }
        
         l2->next=mergeTwoLists(l2->next,l1);
            return l2;
        
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL) return list2;
        if(list2 == NULL) return list1;
        
        ListNode dummy(INT_MIN);
        ListNode* result = &dummy;
        
        while(list1 != NULL && list2 != NULL){
            if(list1->val > list2->val){
                result->next = list2;
                list2=list2->next;
            }
            else{
                result->next = list1;
                list1=list1->next;
            }
            result=result->next;
            
        }
        
        if(list2 == NULL){
            while(list1 != NULL){
                result->next=list1;
                list1=list1->next;
                result=result->next;
            }
        }
        else if(list1 == NULL){
            while(list2 != NULL){
                result->next=list2;
                list2=list2->next;
                result=result->next;
            }
        }
        
        result->next = NULL;
        return dummy.next;
        
    }
};

 

느낀점

오랜만에 해서 그래도 몇시간동안 붙잡고 해냈다는 게 컸다.

재귀가 너무 약하다는 생각이 들었다.

leet code의 learn 부분에 recursion i, ii 있는데 learn부분에 있는 것은 다 풀어봐야겠다고 생각이 들었다.

조잡하게 풀어서 좀 아쉽긴 하다 ㅎ