算法题，c++，分治算法，合并K个升序链表，原链表修改链接顺序降低空间复杂度，分治合并降低时间复杂度

算法题，c++，分治算法，合并K个升序链表，原链表修改链接顺序降低空间复杂度，分治合并降低时间复杂度

题目：leetcode
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

链表结点结构：

typedef struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) { }
ListNode(int x) : val(x), next(nullptr) { }
ListNode(int x, ListNode *next) : val(x), next(next) { }
}ListNode;


思路：
1、K个链表数据量很大，不适合新建容器或新建链表然后排序，可以利用链表本身的next属性，改变每个结点的后接结点，以达到节省空间的效果。
2、K个链表同时对首结点的数据进行比较不方便，如果是两个链表就可以很方便的使用if进行判断，因此在K个链表中两两相合，两两相合的结果再次两两相合，合到只有一个链表，就是最终的结果了。

代码与每一行的注释，一定注意看注释，看注释，不然有可能看不懂代码的：

//合并两个链表为一个链表
ListNode* AddToOne(ListNode* AList, ListNode* BList)
{
//判断是否传入的两个链表中有空的链表
if (!AList || !BList)
{
return (AList ? AList : BList);
}
//用于组合新链表的链表头
ListNode* Tail;
//链表头不能直接使用，新建一个临时结点提供给链表头
//这个空链表头还用于找到链表的头，避免在合并完以后无法获取到链表的起点
//临时结点还用于返回链表头，通过return Head.next
ListNode Head;
Tail = &Head;
//用于遍历两个链表的所有内容和比较链表结点数据的指针
ListNode* pA = AList;
ListNode* pB = BList;
//当两个遍历的结点A，B都有值时，说明两个链表中的数据还没有遍历完，
//只要有一个遍历完了，就表示两个合并为一个了，且无法继续进行比较了
//因此while循环的判断条件是两个结点都有值而不是空
while (pA && pB)
{
//哪个小就把哪个放到新链表的尾部
if (pA->val < pB->val)
{
Tail->next = pA;
pA = pA->next;
}
else
{
Tail->next = pB;
pB = pB->next;
}
//装入尾部后将新链表的当前结点向后移，保持在最后位
Tail = Tail->next;
}
//判断结束后，一个链表变成空了，剩下还有一部分链表需要另外加入到新链表
Tail->next = (pA ? pA : pB);
return Head.next;
}
//使用分治算法将链表vector进行分治合并
//每一次合并只能合并两个下标的链表，将两个链表的所在下标表示为left，right
ListNode* merge(vector<ListNode*>& Data,int left,int right)
{
//当左下标和右下标相等时，返回该下标对应的链表就可以
if (left == right)
{
return Data[left];
}
//当左下标和右下标紧跟着时，就可以合并了，然后将合并的结果返回
else if(left + 1 == right)
{
return AddToOne(Data[left], Data[right]);
}
//当左下标和右下标没有相等，没有紧跟着时，递归下去
//向下递归的规律为：从最左边到中间的合并，中间后一个结点到最右边的合并，得到的两个链表合并后将链表返回
else
{
return AddToOne(merge(Data, left, (left + right) / 2 ), merge(Data, (left + right) / 2 + 1, right));
}
}
ListNode* mergeKLists(vector<ListNode*>& Data)
{
//传入的vector有可能是个空的，为了避免后面的size-1为负数，有必要对size的值进行判断
if (Data.size() == 0)
{
return NULL;
}
return merge(Data, 0, Data.size() - 1);
}