算法题，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);
}