23. Merge k Sorted Lists
- Brush the warehouse address
- 4. Median of Two Sorted Arrays
- 10. Regular Expression Matching
- 23. Merge k Sorted Lists
23. Merge k Sorted Lists
Description
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example
1Input:
2[
3 1->4->5,
4 1->3->4,
5 2->6
6]
7Output: 1->1->2->3->4->4->5->6Copy the codeTranslation
Merge k sorted link lists and return them as a sorted list. Analyze and describe the complexity.
Ideas
Divide and conquer plus merge sort. Branch the array until there are two lists in each group, and merge the two lists.
Note
Accept Code
1/** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9public class MergekLists { 10 public ListNode mergeKLists(ListNode[] lists) { 11 if (lists == null || lists.length == 0) { 12 return null; 13 } 14 return divide(0, lists.length - 1, lists); 15 } 16 17 private ListNode divide(int start, int end, ListNode[] listNodes) { 18 if (start == end) { 19 return listNodes[start]; 20 } 21 ListNode left = divide(start, (start + end) / 2, listNodes); 22 ListNode right = divide((start + end) / 2 + 1, end, listNodes); 23 return mergeTwoLists(left, right); 24 } 25 26 public ListNode mergeTwoLists(ListNode leftList, ListNode rightList) { 27 if (leftList == null) return rightList; 28 if (rightList == null) return leftList; 29 30 if (leftList.val < rightList.val) { 31 leftList.next = mergeTwoLists(leftList.next, rightList); 32 return leftList; 33 } else { 34 rightList.next = mergeTwoLists(leftList, rightList.next); 35 return rightList; 36} 37} 38} 39Copy the codeLink to this article: zdran.com/20180329.ht…