题解 | #合并k个已排序的链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeHelp(ListNode* head1,ListNode* head2){		//合并两个有序链表
        if(head1 == nullptr)
            return head2;
        if(head2 == nullptr)
            return head1;
        ListNode* newHead = head1->val >= head2->val ? head2 : head1;		//头节点值小的作为新的头节点
        ListNode* otherHead = head1->val >= head2->val ? head1 : head2;		//选定另一个链表
        ListNode* cur1 = newHead->next, * cur2 = otherHead;
        ListNode* cur1_pre = newHead;
        while(cur1 && cur2){
            if(cur1->val >= cur2->val){  //把cur2的当前节点插入到cur1的前一个位置
                cur1_pre->next = cur2;  
                cur2 = cur2->next;    
                cur1_pre->next->next = cur1;   //把新加的节点后继连向cur1节点
                cur1_pre = cur1_pre->next;  //cur1_pre确保始终在cur1的前一个节点
            }else{
                cur1_pre = cur1;    
                cur1 = cur1->next;
            }
        }
      //这里如果cur1没到空，说明cur2的最大值小于cur1的最大值，我们又选定cur1作为新链表的头节点，所以可以直接返回
      //如果cur2没到空，说明cur2的最大值大于cur1的最大值，所以要把cur1的最后一个节点连向当先cur2的位置
      */
        if(cur2){
            cur1_pre->next = cur2;
        }
        return newHead;
    }
    
    //归并排序算法
    ListNode* merge(vector<ListNode *> &lists,int l,int r){
        if(l > r)
            return nullptr;
        if(l == r)
            return lists[l];
        int mid = l + ((r - l)>>1);   //求中间值，防止溢出，这里注意运算符的优先级，用括号就无须考虑。
        ListNode* p = merge(lists,l,mid);
        ListNode* q = merge(lists,mid+1,r);
        return mergeHelp(p,q);
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int size = lists.size();
        if(size == 0)
            return nullptr;
        if(size == 1)
            return lists[0];
        return merge(lists,0,size-1);

    }
};
};