首页 / JAVA / Java for LeetCode 023 Merge k Sorted Lists

Java for LeetCode 023 Merge k Sorted Lists

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java for LeetCode 023 Merge k Sorted Lists，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1540字，纯文字阅读大概需要3分钟。

内容图文

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解题思路一：

之前我们有mergeTwoLists(ListNode l1, ListNode l2)方法，直接调用的话，需要k-1次调用，每次调用都需要产生一个ListNode[]，空间开销很大。如果采用分治的思想，对相邻的两个ListNode进行mergeTwoLists，每次将规模减少一半，直到规模变为2为止，空间开销就会小很多。JAVA实现如下：

	static public ListNode mergeKLists(ListNode[] lists) {
		if (lists.length == 0)
			return null;
		if (lists.length == 1)
			return lists[0];
		if (lists.length == 2)
			return mergeTwoLists(lists[0], lists[1]);//参考Java for LeetCode 021 Merge Two Sorted Lists
		else {
			ListNode[] halfLists = new ListNode[lists.length / 2];
			if (lists.length % 2 == 0)
				for (int i = 0; i < halfLists.length; i++)
					halfLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
			else {
				for (int i = 0; i < halfLists.length; i++)
					halfLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
				halfLists[0] = mergeTwoLists(halfLists[0],lists[lists.length - 1]);
			}
			return mergeKLists(halfLists);
		}
	}

 解题思路二：

采用优先级队列，JAVA实现如下：

	public ListNode mergeKLists(ListNode[] lists) {
		Queue<ListNode> heap = new PriorityQueue<ListNode>(
				new Comparator<ListNode>() {
					public int compare(ListNode l1, ListNode l2) {
						return l1.val - l2.val;
					}
				});
		ListNode dummy = new ListNode(0), cur = dummy, tmp;
		for (ListNode list : lists)
			if (list != null)
				heap.offer(list);
		while (!heap.isEmpty()) {
			tmp = heap.poll();
			cur.next = tmp;
			cur = cur.next;
			if (tmp.next != null)
				heap.offer(tmp.next);
		}
		return dummy.next;
	}

 

原文：http://www.cnblogs.com/tonyluis/p/4474240.html

内容总结

以上是互联网集市为您收集整理的Java for LeetCode 023 Merge k Sorted Lists全部内容，希望文章能够帮你解决Java for LeetCode 023 Merge k Sorted Lists所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1265980.html

来源：【匿名】