- 浏览: 173230 次
- 性别:
- 来自: 济南
文章分类
最新评论
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Merge k个有序链表,之前做过一道题目是merge两个有序的链表,这里我们用分治的思想,用归并排序解决。先将k个链表递归的分为两部分,直到剩下两个链表,然后将两个链表合并起来。因为有k个list,假设每个list中有n个元素,那么时间复杂度为O(nk*logk). 代码如下:
Merge k个有序链表,之前做过一道题目是merge两个有序的链表,这里我们用分治的思想,用归并排序解决。先将k个链表递归的分为两部分,直到剩下两个链表,然后将两个链表合并起来。因为有k个list,假设每个list中有n个元素,那么时间复杂度为O(nk*logk). 代码如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; return helper(0, lists.length - 1, lists); } private ListNode helper(int l, int r, ListNode[] lists) { if(l < r) { int m = l + (r - l) / 2; return merge(helper(l, m, lists), helper(m + 1, r, lists)); } return lists[l]; } private ListNode merge(ListNode l1, ListNode l2) { if(l1 == null) return l2; if(l2 == null) return l1; ListNode helper = null; if(l1.val > l2.val) { helper = l2; helper.next = merge(l1, l2.next); } else { helper = l1; helper.next = merge(l1.next, l2); } return helper; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
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. 验证回文字符串 Ⅱ