Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
使用分治法,时间复杂度是nlogk, n是所有元素个数的总和,k是k个lists,
这种方法和依次merge每一个list的方法的时间复杂度不同。
如果第一个list有n-k个元素,其余每个list是1个元素,
两两分治合并,每个元素参与了logk次合并,
如果是依次合并(第一个和第二个合并,之后的结果和第三个合并,以此类推),n-k个元素需要参与k次合作,
这样复杂度就会增加。
/** * 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.length == 0){ return null; } return mergeHelper(lists, 0, lists.length - 1); } public ListNode mergeHelper(ListNode[] list, int start, int end){ if (start == end){ return list[start]; } int mid = start + (end - start) / 2; ListNode left = mergeHelper(list, start, mid); ListNode right = mergeHelper(list, mid + 1, end); return mergeTwoSortedList(left, right); } public ListNode mergeTwoSortedList(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while(list1 != null && list2 != null){ if(list1.val < list2.val) { tail.next = list1; tail = list1; list1 = list1.next; }else { tail.next = list2; tail = list2; list2 = list2.next; } } if(list1 != null) { tail.next = list1; } if(list2 != null) { tail.next = list2; } return dummy.next; } }
画了一张图