LeetCode-23 - 정렬 체인 테이블 K 개 결합 - C 언어

방법1: 귀속분치는 귀속적인 방법을 사용하여 수조를 끊임없이 나누어 하나는 둘로 나누고 귀속은 조건까지 수조 중의 원소는 0개 또는 1개이다.분리된 두 개의 체인 시계를 병합 정렬하다.시간의 복잡도는 O(lgN)이고 합병의 시간 복잡도는 O(N)이기 때문에 시간의 복잡도는 O(NlgN)이다.

typedef struct ListNode Node;

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode head;
    head.next = NULL;
    struct ListNode *rear = &head;
    struct ListNode *node = NULL;
    
    while(l1 && l2){
        rear->next = l1->val < l2->val ? l1 : l2; 
        
        if(l1->val < l2->val){
            l1 = l1->next;
        }else{
            l2 = l2->next;
        }
            
        rear = rear->next;
    }
    
    if(l1){
        rear->next = l1;
        
    }
    if(l2){
        rear->next = l2;
    }
    
    
    return head.next;
    
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if(!listsSize){
        return NULL;
    }
    if(listsSize == 1){
        return lists[0];
    }
    
    int mid = listsSize / 2;
    Node *l1 = mergeKLists(lists, mid);
    Node *l2 = mergeKLists(lists+mid, listsSize-mid);
    
    return mergeTwoLists(l1, l2);    
}

방법2: 비귀속 분치 비귀속 방법은 원래의 수조를 사용하여 분치 후 얻은 임시 체인 헤드를 수조에 넣고 모든 순환 수조의 길이를 반으로 줄이고 마지막에 원소에 도착할 때 되돌아오는 체인 헤드이다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode Node;

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode head;
    head.next = NULL;
    struct ListNode *rear = &head;
    struct ListNode *node = NULL;
    
    while(l1 && l2){
        rear->next = l1->val < l2->val ? l1 : l2; 
        
        if(l1->val < l2->val){
            l1 = l1->next;
        }else{
            l2 = l2->next;
        }
            
        rear = rear->next;
    }
    
    if(l1){
        rear->next = l1;
        
    }
    if(l2){
        rear->next = l2;
    }
    
    
    return head.next;
    
}
 


struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    int left_size = listsSize;
    int i, k;
    int cnt;
    
    if(!listsSize){
        return NULL;
    }
    
    while(left_size>1){
        k = left_size;
        cnt = (k+1)/2;
        for(i=0; i= k ? NULL : lists[2*i+1]));
        }
        
        left_size = (left_size+1)/2;
        
    }
    return lists[0];
    
}