/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

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

 * };

 */

class Solution {

public:

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

        if(l1==NULL)//判断有一组为空的情况

            return l2;

        if(l2==NULL)

            return l1;

        if(l1->val>l2->val)//由于我设计的算法问题，需要明确知道第一个值谁小，不妨用l1小，若不满足，就倒一下

            return mergeTwoLists(l2,l1);

        ListNode* res=l1;//保存头指针，留待返回

        while(l2!=NULL)

        {

            while(l1->next!=NULL && l1->next->val<=l2->val)//直到找出l1下一个比当前l2值大的数，且不能为空

                l1=l1->next;

            if(l1->next==NULL)//只要额外判断l1下个为空的情况，这个值肯定不会比l2大

            {

                l1->next=l2;

                break;

            }

            ListNode* l2_next=l2->next;//一定要记住当前l2的下个节点

            l2->next=l1->next;//这里一定要画图，特清晰，不画要崩溃

            l1->next=l2;//注意这里l1指针停在新加入的节点处

            l1=l1->next;

            l2=l2_next;//即便l2为空也不要紧啊

        }

        return res;

    }

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

        int len=lists.size();

        if(len==)//提前写好三种情况，都是个数的最小单位了

            return NULL;

        if(len==)

            return lists[];

        if(len==)

            return mergeTwoLists(lists[],lists[]);

        vector<ListNode*> list1(len/+);//然后分半，防止有奇数，所以下面是len-len/2-1长度

        vector<ListNode*> list2(len-len/-);

        int i=;

        for(;i<len/+;i++)

            list1[i]=lists[i];

        for(;i<len;i++)

            list2[i-len/-]=lists[i];//划分好后

        ListNode* mer1=mergeKLists(list1);//受归并排序的提示，采用递归实现

        ListNode* mer2=mergeKLists(list2);

        return mergeTwoLists(mer1,mer2);

    }

};