23. 合并K个升序链表（学习了java的自定义比较类）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了23. 合并K个升序链表（学习了java的自定义比较类），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2578字，纯文字阅读大概需要4分钟。
内容图文
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
这是目前唯一一题能想到的hard题了，没有用到什么特别高深的思想，就是一把梭！！！
自己的思路和代码：
1.把所有节点给排序了，然后再重新连起来
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class
Solution {
public
ListNode mergeKLists(ListNode[] lists) {
if(lists==null)
{
returnnull;
}
//放到个arraylist里面 然后就直接排序
ListNode HeadFake=new ListNode(-9);
// System.out.println(lists.length);
// System.out.println(lists[0].val);
// System.out.println(lists[1].val);
// System.out.println(lists[2].val);
List<ListNode> list_new = new ArrayList<ListNode>();
for(int i=0;i<lists.length;i++)
{
while(lists[i]!=null)
{
// System.out.println(lists[i].val); list_new.add(lists[i]);
lists[i]=lists[i].next;
}
}
Collections.sort(list_new, new Comparator<ListNode>() {
publicint compare(ListNode a, ListNode b)
{
return (a.val-b.val);
}
});
ListNode new_head=new ListNode(-1);
ListNode NewHeadPtr=new_head;
for (Iterator<ListNode> it = list_new.iterator(); it.hasNext(); ) {
ListNode s = it.next();
NewHeadPtr.next=s;
NewHeadPtr=NewHeadPtr.next;
// System.out.println(s.val); }
// while(new_head.next!=null)
// {
//// System.out.println(new_head.next.val);
// new_head=new_head.next;
// }return new_head.next;
}
}
Leecode和视频的题解思想
1.和我的一样，排序再重连
2.分治合并
class
Solution {
public
:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* merge(vector <ListNode*> &lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};
作者：LeetCode-Solution
视频的思路：
其它：
还有就是发现java不用vector，所以，可以使用List的这个集合，所以有时间要看看java的set了。
原文：https://www.cnblogs.com/William-xh/p/13666437.html
内容总结
以上是互联网集市为您收集整理的23. 合并K个升序链表（学习了java的自定义比较类）全部内容，希望文章能够帮你解决23. 合并K个升序链表（学习了java的自定义比较类）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。