Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
这题我写的太难看了,就直接看网上copy下来的吧,具体是哪里copy过来的我忘记了。几天的思想就是分治。
这题我写的太难看了,就直接看网上copy下来的吧,具体是哪里copy过来的我忘记了。几天的思想就是分治。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if(lists==null || lists.size()==0) return null; return helper(lists,0,lists.size()-1); } private ListNode helper(ArrayList<ListNode> lists, int l, int r) { if(l<r) { int m = (l+r)/2; return merge(helper(lists,l,m),helper(lists,m+1,r)); } return lists.get(l); } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); dummy.next = l1; ListNode cur = dummy; while(l1!=null && l2!=null) { if(l1.val<l2.val) { l1 = l1.next; } else { ListNode next = l2.next; cur.next = l2; l2.next = l1; l2 = next; } cur = cur.next; } if(l2!=null) cur.next = l2; return dummy.next; } }
发表评论
-
Generate Parentheses
2015-03-12 19:50 365Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 308Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 340Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 332Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 312Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 292Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 319Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 328Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 328Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 323Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 367Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 332Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 343Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 255The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 334Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 300You are given two linked lists ... -
Longest Substring Without Repeating Characters
2015-02-11 21:14 425[size=24px;]Longest Substring W ...
相关推荐
LeetCode Merge 2 Sorted Lists解决方案
Merge k Sorted Lists 给定k个有序数组并将其合并成1个有序数组, 代码采用C#编写
第四章 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
21.Merge Two Sorted Lists LeetCode 23.Merge k Sorted Lists(solve1) LeetCode 23.Merge k Sorted Lists(solve2) LeetCode 86.Partition List LeetCode 92.Reverse Linked List II LeetCode 138.Copy List with ...
Merge k Sorted Lists Sort List 快速排序 Sort Colors Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range...
lru缓存leetcode 力扣日记 欢迎来到我的 LeetCode 期刊库。 我的每个问题都将包括一个初始计划...k Sorted Lists (Hard) 31. Next Permutation (Medium) 34. Find First and Last Position of Element in Sorted Arr
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median ...Sorted ...#23:Merge k Sorted Lists
Merge K Sorted Lists Remove Invalid Parentheses Serialize and Deserialize Binary Tree Minimum Window Substring C++ STL中常见容器的时间复杂度 map, set, multimap, and multiset 上述四种容器采用红黑树实现...
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...
【Leetcode】Merge Two Sorted Lists
Lists(合并 k 个排序链表) 英文版: 中文版: Task2(8.5-8.9) 3.栈 用数组实现一个顺序栈 用链表实现一个链式栈 编程模拟实现一个浏览器的前进、后退功能 4.队列 用数组实现一个顺序队列 用链表实现一个链式队列...
多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium ...Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
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
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring ...Sorted ...Merge Two Sorted Lists 简单 链结串列 重要 Remove Duplicates from
Merge Two Sorted Lists 83 Easy Remove Duplicates from Sorted List 141 Easy Linked List Cycle 160 Easy Intersection of Two Linked Lists 203 Easy Remove Linked List Elements no 206 Easy Reverse Linked ...
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 原创文章每周最少两篇,后续最新文章会在首发,视频首发,大家可以加我进交流群,技术交流或提意见都可以,欢迎Star!...Merge Two Sorted Lists 83 * Remove Duplicates from Sorted Lis
leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash 2 Add Two Numbers 两数相加 math 3 Longest Substring ...Sorted ...Merge Two Sorted Lists 合并两个有序链表 lin
java二叉树算法源码 algorithm-primer algorithm primer - 算法基础、Leetcode编程、剑指offer ...Sorted Lists Easy 141 判断链表是是否存在环 Linked List Cycle Easy 142 环形链表II Linked List Cycle I
leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic ...Merge ...Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ