leetcode 23. K 개 정렬 링크 hard 통합

leetcode 23. K 개의 정렬 링크 를 합 칩 니 다.  hard          
제목 설명:
합치다 k 정렬 링크알고리즘 의 복잡 도 를 분석 하고 설명 하 십시오.
문제 풀이 방향:
두 가지 방법의 복잡 도 는 모두 O (nklogk) 이다.
방법 1: 분할 통치하 다
끊 임 없 는 반 구분, 예 를 들 어 k 개의 링크 는 먼저 두 개의 k / 2 개의 링크 를 합병 하 는 임무 로 나 눈 다음 에 끊임없이 아래로 나 누 어 하나 또는 두 개의 링크 만 있 는 임무 로 나 눌 때 까지 합병 을 시작 합 니 다.예 를 들 어 6 개의 링크 를 합병 하면 분 치 법 에 따라 우 리 는 먼저 0 과 3, 1 과 4, 2 와 5 를 합병 한다.이렇게 하면 다음 에는 3 개의 링크 만 합병 하면 우 리 는 1 과 3 을 합병 하고 마지막 에 2 와 합병 하면 된다.코드 중의 k 는 (n + 1) / 2 를 통 해 계 산 된 것 입 니 다. 여기 서 왜 1 을 추가 해 야 합 니까? 이것 은 n 이 홀수 일 때 k 는 항상 후반 부 부터 시작 할 수 있 습 니 다. 예 를 들 어 n = 5 일 때 k = 3 은 0 과 3 이 합 쳐 지고 1 과 4 가 합 쳐 지 며 가장 중간 에 있 는 2 가 비어 있 습 니 다.n 이 짝수 일 때 1 을 더 해도 영향 이 없다. 예 를 들 어 n = 4 일 때 k = 2, 그러면 0 과 2 가 합병 되 고 1 과 3 이 합병 되 어 문 제 를 완벽 하 게 해결한다.
방법 2: 최소 더미
최소 더미 라 는 데이터 구 조 를 사 용 했 습 니 다. 우 리 는 먼저 k 개의 링크 의 첫 번 째 요 소 를 최소 더미 에 넣 으 면 자동 으로 순 서 를 정할 것 입 니 다.그 다음 에 우 리 는 가장 작은 요 소 를 꺼 내 서 우리 의 최종 결과 의 링크 에 넣 은 다음 에 요 소 를 꺼 내 서 다음 에 더미 에 넣 고 다음 에 가장 작은 요 소 를 꺼 내 똑 같은 조작 을 한다. 이런 식 으로 유추 하면 더미 에 요소 가 없 을 때 까지 k 개의 링크 도 하나의 링크 로 합 쳐 첫 번 째 노드 로 돌아 가면 된다.
 tips：priority_queue,decltype(cmp)> pq(cmp); //쓰기 에 주의 하 다
방법 1 코드:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        int n=lists.size();
        if(n==0)
            return nullptr;
        
        while(n>1){
            int k=(n+1)/2;  //                  merge
            for(int i=0;ivalval){
                cur->next=head1;
                head1=head1->next;
            }
            
            else{
                cur->next=head2;
                head2=head2->next;
            }
            
            cur=cur->next; 
        }
        
        if(head1)
            cur->next=head1;
        if(head2)
            cur->next=head2;
        return dummy.next;
    }
    
    
};

방법 2 코드:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        if(lists.empty())
            return nullptr;
        
        auto cmp=[]( ListNode *&a, ListNode *&b){
            return a->val>b->val;  //      ， false     
        };
        
        priority_queue,decltype(cmp)> pq(cmp); //    
        
        for(auto i:lists){
            if(i!=nullptr)
                pq.push(i);
        }
        
        ListNode dummy(0);
        ListNode *pre=&dummy;
        ListNode *cur=nullptr;
        while(pq.size()){
            cur=pq.top();
            pq.pop();
            pre->next=cur;
            if(cur->next) pq.push(cur->next);
            pre=pre->next;
        }
        
        return dummy.next;
        
        
    }
};