[数据结构与算法]23. 合并K个升序链表

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路：首先考虑两个链表合并的方法，【原地修改可以使空间复杂度达到O(1)】 原地调整链表元素的 next 指针完成合并

首先我们需要一个变量 head 来保存合并之后链表的头部，把 head 设置为一个虚拟的头（也就是 head 的 val 属性不保存任何值），这是为了方便代码的书写，在整个链表合并完之后，返回它的下一位置即可。
我们需要一个指针 tail 来记录下一个插入位置的前一个位置，以及两个指针 aPtr 和 bPtr 来记录 a 和 b未合并部分的第一位。
当 aPtr 和 bPtr 都不为空的时候，取 val 熟悉较小的合并；如果 aPtr 为空，则把整个 bPtr 以及后面的元素全部合并；bPtr 为空时同理。
在合并的时候，应该先调整 tail 的 next 属性，再后移 tail 和 *Ptr（aPtr 或者 bPtr）。
有这个方法之后，依次遍历遍历待排序的链表即可。

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
   ListNode * mergeTwoKLists( ListNode * a,ListNode * b)
   {
       if((!a) || (!b)) return a?a:b;
       ListNode head;
       ListNode *ap = a,* bp = b;
       ListNode * temp  = &head;
       while( ap && bp)
       {
           if( ap->val < bp->val)
           {
               temp->next = ap;
               ap = ap->next;
           }else{
               temp->next = bp;
               bp = bp->next;
           }
           temp = temp->next;
       }
       temp->next = (ap?ap:bp);
       return head.next;
   }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode * res = nullptr;
        for( int i = 0; i < lists.size(); ++i)
        {
            res = mergeTwoKLists(res,lists[i]);
        }
        return res;
    }
};