leetcode 23. 合并 K 个升序链表

思路：采用了暴力破解法

1.值收集：遍历 K 个链表的所有节点，将节点值存入数组，把 “链表的有序合并” 转化为 “数组的排序”；
2.数组排序：利用系统排序函数对存储节点值的数组进行升序排序，得到全局有序的数值序列；
3.链表重建：以排序后的数组为基础，逐个创建链表节点并拼接，生成最终的升序链表。

创建一个整型数组，用于存放 链表中所有节点的数值。

链表的优势是 “动态插入删除”，但此处我们需要全局排序，数组的随机访问和排序操作更高效、更易实现。

外层循环：遍历输入的 lists 数组（lists 中每个元素是一个链表的头指针），head 代表当前遍历到的链表的头节点。逐个处理 K 个链表，确保没有遗漏任何一个链表。

内层循环：定义指针，初始指向当前链表的头节点，用于遍历该链表的所有节点。
循环条件 ： 只要指针不指向空（即未到链表末尾），就继续遍历，将当前节点的数值 val 存入数组。然后指针向后移动一位，指向链表的下一个节点，直到遍历到链表末尾。

排序。

然后定义虚拟头节点，避免处理空链表的特殊情况，同时无需单独处理第一个节点的头指针赋值 问题，所有新节点都可以统一拼接到 dummy 之后

定义指针 p，初始指向虚拟头节点 dummy，作为移动指针，负责逐个拼接新创建的链表节点，避免频繁修改头指针。

最后返回dummy.next，因为dummy是虚拟头节点，他的后一个才是真正的头节点

时间复杂度：O(NlogN)
遍历所有节点收集值：O(N)（N 为所有节点的总数，每个节点仅访问一次）；
数组排序：O(NlogN)（sort 函数的时间复杂度）；
重建链表：O(N)（每个数值仅创建一次节点）；
总复杂度由最高项决定，即 O(NlogN)。

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {//用listnode表示链表时，ListNode * 默认代表链表头

vector<int> a;

for(ListNode* head:lists){//外层循环遍历lists数组中每个链表的头指针

ListNode* p=head;

while(p!=nullptr){//内层循环遍历当前链表的每个节点，到链表末尾

a.push_back(p->val);

p=p->next;

}

}

sort(a.begin(),a.end());

ListNode dummy(0);//创建一个虚拟头节点

ListNode* q=&dummy;

for(int b:a){

q->next=new ListNode(b); //用当前数值创建新节点，接在q指针之后

q=q->next;

}

return dummy.next;

}

};

这个方法的核心是通过收集所有节点值→排序数组→重建链表的三步操作，把合并 K 个有序链表转化为更易实现的数组操作。

它的优势是思路直观、代码好写，用数组排序规避了复杂的链表指针操作，虚拟头节点还能处理空链表等边界情况；缺点是需要额外数组空间，时间复杂度为O(NlogN)（N 是总节点数），适合小规模数据或快速实现的场景。