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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    // 两个有序链表排序
    ListNode* merge2Lists(ListNode* p1,ListNode* p2){
	// 针对两个特殊情况处理
        if (p1==nullptr){
            return p2;
        }
        if (p2==nullptr){
            return p1;
        }
	// 双指针遍历完升序数组
        ListNode* result_head=new ListNode(0);
        ListNode* current_ptr=result_head;
        while (p1 && p2) {
            if (p1->val<=p2->val){
                current_ptr->next=p1;
                p1=p1->next;
            }else{
                current_ptr->next=p2;
                p2=p2->next;
            }
            current_ptr=current_ptr->next;
        }
        if (p1!=nullptr) {
            current_ptr->next=p1;
        }
        if (p2 != nullptr){
            current_ptr->next=p2;
        }
        return result_head->next;
    }

    
    // 归并算法划分区间函数
    ListNode* splitList(vector<ListNode*>& lists,int left,int right){
        if (left>right) {
            return nullptr;
        }else if (left==right) {
            return lists[left];
        }

        int mid=(left+right)/2;
	// 使用归并思路,划分区间,然后每个区间进行排序
        return merge2Lists(splitList(lists, left,mid),splitList(lists,mid+1,right));
    }



    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        return splitList(lists,0,lists.size()-1);
    }
};

暴力算法可以参考合并两个升序链表，但是时间过不去；可以参考归并排序思路，先划分小区间然后每个小区间排序，有了思路这道题就简单了。