力扣：23,-合并K个升序链表

题目描述

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

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

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]
 

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode）

题目链接：力扣-23.合并k个升序链表

解题思路

前置知识：力扣：21-合并两个有序链表_真的没事鸭的博客-CSDN博客 

这道题我们把链表两两结合，如果会合并两个有序链表的话，这道题应该很容易就能想出来，不过是稍微绕了一点弯子而已，本质还是合成两个有序链表的问题。

我们创建一个ans链表和一个head链表，ans链表就是我们最后返回的结果，head一直指向两个链表合并之后的头结点，然后我们让ans和vector中的链表进行合并，建立一个res链表用来存储两个链表合并后的结果，合并之后我们让ans继续指向head，然后再继续和vector中的链表进行合并。

这样最后ans就是所要求的的链表了。

代码实现

/**
 * 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* mergeKLists(vector& lists) {
        ListNode* ans=new ListNode();
        ListNode* head;//一直指向res的头结点
        for(int i=0;isize();i++)
        {
            ListNode* res=new ListNode();//存储两个链表合并后的结果
            head=res;//将head指向res
            merge(ans->next,lists[i],res);
            ans=head;//将ans指向合并链表后的头结点
        }
        return ans->next;
    }
    //合并两个链表的相关操作
    void merge(ListNode* &list1,ListNode* &list2,ListNode* &ans)
    {
        while(list1&&list2)
        {
            if(list1->val>list2->val)
            insert(list2,ans);
            else
            insert(list1,ans);
        }
        while(list1)
        insert(list1,ans);
        while(list2)
        insert(list2,ans);
    }
    //将一个节点的值插入到另外一个链表
    void insert(ListNode* &list,ListNode* &ans)
    {
        ans->next=list;
        ans=ans->next;
        list=list->next;
    }
 
};