/**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

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

  * };

  */

 class Solution {

 public:

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

         int mid = lists.size() / ;

         ListNode* l1 = mergeK(lists, , mid - );

         ListNode* l2 = mergeK(lists, mid, lists.size() - );

         return merge(l1, l2);

     }

     ListNode* mergeK(vector<ListNode*>& lists, int start, int end) {

         if(start == end) return lists[start];

         else if(start < end){

             int mid = (start + end) / ;

             ListNode* l1 = mergeK(lists, start, mid);

             ListNode* l2 = mergeK(lists, mid + , end);

             return merge(l1, l2);

         }

         else return NULL;

     }

     ListNode* merge(ListNode* l1, ListNode* l2){

         if(l1 == NULL) return l2;

         if(l2 == NULL) return l1;

         if(l1->val > l2->val) return merge(l2, l1);

         ListNode* head = l1;

         while(l2 && l1->next){

             if(l1->next->val > l2->val){

                 ListNode* next = l2->next;

                 l2->next = l1->next;

                 l1->next = l2;

                 l2 = next;

             }

             l1 = l1->next;

         }

         if(l2) l1->next = l2;

         return head;

     }

 };