This is the 14th day of my participation in the August More Text Challenge. For details, see:August is more challenging
Today is also a rare early Saturday, it is raining outside and I don’t want to go anywhere, cooking, reading and watching TV, so I should spend the weekend lazy. In the morning, I read the technical blog of Meituan for a while. The articles above are very good. They are either pure technology full of dry goods, or deep thinking. The gap is still very big, but write a daily practice, should be able to write a good article gradually.
Today is the 23rd problem of Leetcode, the difficulty of calibration is difficult, but in fact, there are a few days before the 1 problem is similar to pave the way, also good.
The title
You are given an array of linked lists, each of which has been sorted in ascending order. Please merge all lists into an 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 – > 6
Example 2: Input: lists = [] Output: []
Example 3: Input: lists = [[]] Output: []
Train of thought
A few days ago, there was a question about merging 2 ascending linked lists, today’s question is merging K. Now that we have a way to merge the two lists, it’s a lot easier. (Merge 2 ascending list of problems see “Leetcode – Merge two ordered lists”). You can take the idea of divide and conquer, you want to divide a big problem into two small problems, and then merge the solutions of the two small problems, and this idea can be recursively repeated, subproblems can be divided into smaller subproblems, and as long as you have the ability to merge the solutions of the subproblems, you can keep dividing until you have a problem that already has a solution. In this case, you can go from bottom to top, first 22 merge, to the top 1 layer, and then merge the results of the merge again 22, until the merge into a large list.
In fact, there is a simple algorithm idea here, which is to transform the problem of unknown solution into a problem of known solution, and then directly reuse the known solution. Problem 1 is to boil a pot of boiling water. The known solution is to first take an empty kettle, fill it with water, put it on a gas cooker, turn on the gas, and then turn off the gas cooker after the water boils. To solve problem 2, if the kettle is full of water, how to boil a pot of water? Somebody said, let’s just pour the water out, and then we get to problem number one. At first, I would laugh at this joke. On second thought, although this solution looks silly, it is actually the second best solution, or even the best solution in some cases. And the nice thing about this is that we can directly view the solution to problem 1 as a black box, so we don’t have to worry about the solution to problem 1, as long as we know that we have a solution to problem 1, and when we solve problem 2, it only takes us one step, which is to pour the water out of the kettle, to turn problem 2 into problem 1, which we know. How to quickly transform a problem into a known solution of the problem, is also a program ape must have the ability.
Back to this topic, we use the partition, continuously to this list of arrays, eventually it points to the merger of two linked list has problem, so you can directly use known solution of 2 days ago, standing on the shoulders of our predecessors.
Java version code
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { int len = lists.length; return mergeKLists(lists, 0, len - 1); } private static ListNode mergeKLists(ListNode[] lists, int startIndex, int endIndex) { if (startIndex > endIndex) { return null; } if (startIndex == endIndex) { return lists[startIndex]; } int mid = (startIndex + endIndex) / 2; return mergeTwoLists(mergeKLists(lists, startIndex, mid), mergeKLists(lists, mid + 1, endIndex)); } public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; }}}Copy the code