/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* merge(ListNode* left, ListNode* right){   //归并操作

        if(left==NULL) return right;

        if(right==NULL) return left;

        ListNode *ans =new ListNode();

        if(left->val <= right->val){

            ans=left;

            left = left->next;

        }else{

            ans=right;

            right=right->next;

        }

        ans->next = merge(left,right);

        return ans;

    }

    ListNode* mergesort(vector<ListNode *> &lists,int left,int right){  //devide && conquer

        if(left>right){

            return NULL;

        }if(left==right){

            return lists[left];

        }else{

            int middle = (left+right)>>;

            ListNode *lleft = mergesort(lists,left,middle);

            ListNode *lright = mergesort(lists,middle+,right);

            return merge(lleft,lright);

        }

    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {

        int left =,right =lists.size()-;

        int middle= (left+right)>>;

        ListNode *lleft = mergesort(lists,left,middle);

        ListNode *lright = mergesort(lists,middle+,right);

        return merge(lleft,lright);

    }

};