`
huntfor
  • 浏览: 205227 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Merge k Sorted Lists

 
阅读更多

新博文总结了三种算法,新博文地址:[leetcode]Merge k Sorted Lists

Merge k Sorted Lists

 

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

 K路归并,不知道大家对2路归并还有木有印象,如果木有的话,请戳这里

其实K路归并,就是进行k - 1 次二路归并,完全一样。

代码如下:

public ListNode mergeKLists(ArrayList<ListNode> lists){
		ListNode result = new ListNode(0);
		if(lists == null || lists.size() == 0 ){
			return null;
		}
		if(lists.size() == 1){
			return lists.get(0);
		}
		result = merge2List(lists.get(0),lists.get(1));
		for(int i = 2; i < lists.size();i++){
			result = merge2List(result,lists.get(i));
		}
		return result;
	}

	private ListNode merge2List(ListNode l1,ListNode l2){
		ListNode l1Tail = l1;
		ListNode l2Tail = l2;
		ListNode list = new ListNode(0);
		ListNode tail = list;
		while(l1Tail != null || l2Tail != null){
			if(l1Tail == null){
				tail.next = l2Tail;
				break;
			}
			if(l2Tail == null){
				tail.next = l1Tail;
				break;
			}
			if(l1Tail.val < l2Tail.val){
				tail.next = l1Tail;
				l1Tail = l1Tail.next != null ? l1Tail.next : null;;
			}else{
				tail.next = l2Tail;
				l2Tail = l2Tail.next != null ? l2Tail.next : null;
			}
			tail = tail.next;
					
		}
		return list.next;
	}

 

分享到:
评论
4 楼 huntfor 2014-06-28  
249326109 写道
huntfor 写道
249326109 写道
这种方法的复杂度有没有算过,想想更优的的解法。

为毛跑到开源中国开博客啊,Iteye干嘛不用?

一天只能发5篇博客怎么破。。

写草稿,第二天发,这个没办法
3 楼 249326109 2014-06-27  
huntfor 写道
249326109 写道
这种方法的复杂度有没有算过,想想更优的的解法。

为毛跑到开源中国开博客啊,Iteye干嘛不用?

一天只能发5篇博客怎么破。。
2 楼 huntfor 2014-06-25  
249326109 写道
这种方法的复杂度有没有算过,想想更优的的解法。

为毛跑到开源中国开博客啊,Iteye干嘛不用?
1 楼 249326109 2014-06-25  
这种方法的复杂度有没有算过,想想更优的的解法。

相关推荐

    LeetCode Merge 2 Sorted Lists解决方案

    LeetCode Merge 2 Sorted Lists解决方案详解 Merge 2 Sorted Lists是LeetCode上的一个经典算法题目,旨在考察程序员对链表的操作和排序算法的掌握程度。下面对该题目的解决方案进行详细的分析和解释。 问题描述 ...

    c语言-leetcode 0023-merge-k-sorted-lists.zip

    c c语言_leetcode 0023_merge_k_sorted_lists.zip

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters ...23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    c语言-leetcode 0021-merge-two-sorted-lists.zip

    c c语言_leetcode 0021_merge_two_sorted_lists.zip

    js-leetcode题解之23-merge-k-sorted-lists.js

    最终,题解文件“js-leetcode题解之23-merge-k-sorted-lists.js”将为leetcode用户和JavaScript开发者提供一个清晰的解题思路和一个可靠的代码实现,帮助他们更好地理解和掌握如何合并多个排序链表,以及如何在实际...

    leetcode中文版-LeetCode:力码

    leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...

    C语言-leetcode题解之21-merge-two-sorted-lists.c

    “C语言-leetcode题解之21-merge-two-sorted-lists.c”不仅为初学者提供了一道链表操作的经典题目,更是引导其深入理解链表结构和指针操作的一个有效途径。通过不断的练习和思考,可以快速提升编程能力和解题技巧,...

    MergeTwoSortedLinkedList.java

    【Leetcode】Merge Two Sorted Lists

    js-leetcode题解之21-merge-two-sorted-lists.js

    今日我们要分析的题目是LeetCode上的一道经典题目——合并两个有序链表(Merge Two Sorted Lists)。该题目要求编写一个函数,将两个已排序的链表合并为一个新的有序链表,并且返回新的链表头节点。这里提到的链表是...

    leetcode分类-leetcode:leetcode问题的代码

    leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median ...Sorted ...#23:Merge k Sorted Lists

    lrucacheleetcode-leetcode-journal:记录所有LeetCode挑战的存储库

    lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划...k Sorted Lists (Hard) 31. Next Permutation (Medium) 34. Find First and Last Position of Element in Sorted Arr

    Leetcode book刷题必备

    23. Merge K Sorted Lists:合并 k 个排序链表。 24. Copy List with Random Pointer:复制带有随机指针的链表。 【二叉树】 25. Validate Binary Search Tree:验证二叉搜索树。 26. Maximum Depth of Binary Tree...

    LeetCode 刷题汇总1

    * 合并两个排序列表(Merge Two Sorted Lists):合并两个排序列表。 * 搜索插入位置(Search Insert Position):在排序数组中搜索插入位置。 8. 动态规划: * 3Sum(3Sum):找到数组中三个元素的和等于目标值...

    leetcode答案-LeetCode:Swift中的LeetCode

    Merge Two Sorted Lists Easy #26 Remove Duplicates from Sorted Array Easy #27 Remove Element Easy #35 Search Insert Position Easy #38 Count and Say Easy #53 Maximum Subarray Easy #66 Plus One Easy #70 ...

    leetcode添加元素使和等于-leetcode:我的leetcode解决方案

    leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode leetcode ...Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3

    leetcode2-Leetcode:Leetcode_answer

    leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。...Merge Two Sorted Lists JavaScript O(n)

    c语言-c语言编程基础之leetcode题解第23题合并K个升序链表.zip

    本题来自著名的在线编程挑战平台LeetCode,题号为第23题,名为“Merge K Sorted Lists”(合并K个升序链表)。这是一道典型的数据结构与算法题目,主要考察的是链表操作和排序技巧。 链表是计算机科学中常用的一种...

    LeetCode最全代码

    26 | [Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp) [Python](./Python/remove-duplicates...

Global site tag (gtag.js) - Google Analytics