问题:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
官方难度:
Hard
翻译:
合并k个已排序的链表,得到一个新的链表并且返回其第一个节点。分析并阐述其复杂度。
- 这是No.021(Merge Two Sorted Lists)的深入研究。
- 可以借鉴归并排序的思想,对于长度为k的数组,依次进行二路归并,返回这两个链表合并之后的头结点(利用No.021现成的代码),下次递归时,入参为长度为(k+1)/2的头结点数组。
- 在k为奇数时,先去掉最后一项,剩余项依次二路归并,再将最后一项放入新的数组。
- 由于使用递归,所以将递归方法独立出来,因为只要做依次入参检查即可。
- 算法的复杂度与归并排序相同,即O(nlogn)的时间复杂度,O(n)的空间复杂度。
解题代码:
1 public static ListNode mergeKLists(ListNode[] lists) { 2 if (lists == null) { 3 throw new IllegalArgumentException("Input error"); 4 } 5 if (lists.length == 0) { 6 return null; 7 } 8 return mergeListsArray(lists); 9 } 10 11 // 合并 k 个有序链表 12 public static ListNode mergeListsArray(ListNode[] lists) { 13 // 递归终点 14 if (lists.length == 1) { 15 return lists[0]; 16 } 17 // 下一次递归的头结点数组 18 ListNode[] next = new ListNode[(lists.length + 1) >>> 1]; 19 // 二路归并 20 if (lists.length % 2 == 0) { 21 for (int i = 0; i < lists.length; i += 2) { 22 next[i >>> 1] = merge2Lists(lists[i], lists[i + 1]); 23 } 24 } else { 25 for (int i = 0; i < lists.length - 1; i += 2) { 26 next[i >>> 1] = merge2Lists(lists[i], lists[i + 1]); 27 } 28 next[next.length - 1] = lists[lists.length - 1]; 29 } 30 return mergeListsArray(next); 31 } 32 33 // 合并2个有序链表 34 private static ListNode merge2Lists(ListNode l1, ListNode l2) { 35 if (l1 == null) { 36 return l2; 37 } 38 if (l2 == null) { 39 return l1; 40 } 41 // 返回的第一个节点 42 ListNode first = l1.val > l2.val ? l2 : l1; 43 // 上一个节点 44 ListNode last = new ListNode(0); 45 while (true) { 46 if (l1.val > l2.val) { 47 // 交换l1节点和l2节点,保证下一次循环仍然以l1节点为基准 48 ListNode swapNode = l2; 49 l2 = l1; 50 l1 = swapNode; 51 } 52 // 将last节点的next指针指向l1,同时更新last 53 last.next = l1; 54 last = l1; 55 // 带排序的链表遍历完成,剩余链表自然有序 56 if (l1.next == null) { 57 l1.next = l2; 58 break; 59 } 60 l1 = l1.next; 61 } 62 return first; 63 }
相关链接:
https://leetcode.com/problems/merge-k-sorted-lists/
PS:如有不正确或提高效率的方法,欢迎留言,谢谢!