题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
解题思路
这个题目显然是可以用归并排序（区间内单调）的方法——最核心的地方就是合并两个有序链表（力扣第21）
同时也可以用优先级队列的方法，不过要修改比较方法（仿函数）。在优先级队列的方法中，有一个很重要的点，就是把所以节点的后续节点（next）制空，避免出现节点指向出现问题。
代码
归并排序
/** * 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<ListNode*>& lists) { if(lists.size()==0) return nullptr; return merge(lists,0,lists.size()-1); } ListNode* merge(vector<ListNode*>& lists,int left,int right) { if(left==right) return lists[left]; int mid=(left+right)>>1; ListNode* l=merge(lists,left,mid); ListNode* r=merge(lists,mid+1,right); ListNode* phead=new ListNode; ListNode* cur=phead; //合并两个有序链表 while(l&&r) { if(l->val<r->val) cur->next=l,l=l->next; else cur->next=r,r=r->next; cur=cur->next; } if(l) cur->next=l; else cur->next=r; return phead->next; } };
优先级队列
/** * 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 { struct cmp { bool operator()(ListNode* a,ListNode* b) { if(a->val<b->val) return false; return true; } }; public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*,vector<ListNode*>,cmp> pq; for(auto cur:lists) { while(cur) { pq.push(cur); cur=cur->next; } } ListNode* phead=new ListNode; ListNode* cur=phead; while(pq.size()!=0) { //重点，最关键 pq.top()->next=nullptr; cur->next=pq.top(); cur=cur->next; pq.pop(); } return phead->next; } };
