原题链接在这里:https://leetcode.com/problems/merge-k-sorted-lists/
题目:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题解:
是Merge Two Sorted Lists的进阶版,现在是k条,用divide and conquer, 两条两条合并 最后合并成一个大的。
Note: mergeSort中别忘了最后的返回值是lists[l].
分析时间复杂度T(k) = 2T(k/2) + O(nk). k = lists.length, n是原数组中最长的list的长度。根据master theorem, Time Complexity: O(nk*logk).
Space: O(logk) 是recursion tree的高度。
AC Java:
/** * 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 mergeSort(lists, 0, lists.length-1); } private ListNode mergeSort(ListNode[] lists, int l, int r){ if(l == r){ return lists[l]; } int m = l+(r-l)/2; ListNode leftList = mergeSort(lists, l, m); ListNode rightList = mergeSort(lists, m+1, r); return merge(leftList, rightList); } private ListNode merge(ListNode l1, ListNode l2){ if(l1 == null){ return l2; } ListNode dummy = new ListNode(0); ListNode cur = dummy; while(l1 != null && l2 != null){ if(l1.val <= l2.val){ cur.next = l1; l1 = l1.next; cur = cur.next; }else{ cur.next = l2; l2 = l2.next; cur = cur.next; } } if(l1 != null){ cur.next = l1; } if(l2 != null){ cur.next = l2; } return dummy.next; } }