Nuggets team number online, help you Offer impromptu! Click to view spring recruitment positions in big factories
I. Title Description:
You are given an array of linked lists, each of which has been sorted in ascending order.
Please merge all lists into one ascending list and return the merged list.
Example 1:
Input: lists = [].enlighened by [1 4], [2, 6]] output:,1,2,3,4,4,5,6 [1] : list array is as follows: [1 - > > 5, 4-1 - > 3 - > 4, 6] 2 - > merge them into an ordered list. 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the codeExample 2:
Input: Lists = [] Output: []Copy the codeExample 3:
Input: Lists = [[]] Output: []Copy the codeSubject address: leetcode-cn.com/problems/me…
Ii. Analysis of Ideas:
Is violent, traverse the list array, two of the face, in turn, to merge, but it will encounter a problem, when incorporated into a period of time, there will be a linked list is very long, the other a linked list is very short, in extreme cases, may need to traverse a long list of all nodes, rising time complexity. It’s better to do a divide-and-conquer mentality, divide and conquer the array, until you have two lists in each group, and then merge and sort those two lists.
Iii. AC Code:
public class MergekLists { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return divide(0, lists.length - 1, lists); } private ListNode divide(int start, int end, ListNode[] listNodes) { if (start == end) { return listNodes[start]; } ListNode left = divide(start, (start + end) / 2, listNodes); ListNode right = divide((start + end) / 2 + 1, end, listNodes); return mergeTwoLists(left, right); } public ListNode mergeTwoLists(ListNode leftList, ListNode rightList) { if (leftList == null) return rightList; if (rightList == null) return leftList; if (leftList.val < rightList.val) { leftList.next = mergeTwoLists(leftList.next, rightList); return leftList; } else { rightList.next = mergeTwoLists(leftList, rightList.next); return rightList; }}}Copy the codeIv. Summary:
Note that we are working directly on the original list, so recursion can be used. If you’re creating a new list, you have to worry about processing the results.