Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how C++ merges k ordered linked lists". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Merge k Sorted Lists merges k ordered linked lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:

[

1-> 4-> 5

1-> 3-> 4

2-> 6

]

Output: 1-> 1-> 2-> 3-> 4-> 4-> 5-> 6

This problem allows us to merge k ordered lists, and the final result must also be ordered. We have done a Merge Two Sorted Lists before, which is to mix and insert two ordered lists. This problem makes it more difficult to merge k ordered linked lists, but no matter how many are merged, it is basically necessary to merge in pairs. Then the first consideration is whether we can use the solution of the previous problem to solve this problem. The answer is yes, but it needs to be modified. How to modify it? the first thing that comes to mind is a pairwise merger, that is, the first two are merged first, then the third, and then the fourth until the k. This is the right way of thinking, but the efficiency is not high, can not pass the OJ, so we can only change the way of thinking, here we need to use the divide and conquer method Divide and Conquer Approach. To put it simply, it is a constant half-and-half division, for example, k linked lists are divided into tasks that merge two k big 2 linked lists, and then continue to divide until tasks with only one or two linked lists begin to merge. For example, if you merge 6 linked lists, you will first merge 0 and 3, 1 and 4, respectively, according to the divide-and-conquer method. So next time you only need to merge 3 linked lists, then merge 1 and 3, and finally merge with 2. The k in the code is calculated by (nasty 1) / 2, so why add 1 here, so that when n is odd, k can always start from the second half, for example, when nasty 5, then knot 3, then 0 and 3 merge, 1 and 4 merge, the middle 2 is empty. When n is even, adding 1 will not affect it. For example, when n is even, then kryp2, then 0 and 2 merge, 1 and 3 merge, and the problem is solved perfectly. See the code as follows:

Solution 1:

Class Solution {public: ListNode* mergeKLists (vector& lists) {if (lists.empty ()) return NULL; int n = lists.size (); while (n > 1) {int k = (n + 1) / 2; for (int I = 0; I

< n / 2; ++i) { lists[i] = mergeTwoLists(lists[i], lists[i + k]); } n = k; } return lists[0]; } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1), *cur = dummy; while (l1 && l2) { if (l1->

Val

< l2->

Val) {cur- > next = L1; L1 = L1-> next;} else {cur- > next = L2; L2 = L2-> next;} cur = cur- > next;} if (L1) cur- > next = L1; if (L2) cur- > next = L2; return dummy- > next }}

Let's take a look at another solution, which uses the data structure of the minimum heap. First, all the first elements of the k linked lists are added to the minimum heap, and they are automatically sorted. Then each time the smallest element is added to the linked list of the final result, and then the next element of the extracted element is added to the heap, and the next time the smallest element is taken from the heap to do the same operation, and so on, until there are no elements in the heap. At this time, the k linked lists are also merged into a linked list and return to the first node. See the code as follows:

Solution 2:

Class Solution {public: ListNode* mergeKLists (vector& lists) {auto cmp = [] (ListNode*& a, ListNode*& b) {return a-> val > b-> val;}; priority_queue Q (cmp); for (auto node: lists) {if (node) q.push (node);} ListNode* dummy = new ListNode (- 1), * cur = dummy While (! q.empty ()) {auto t = q.top (); q.pop (); cur- > next = t; cur = cur- > next; if (cur- > next) q.push (cur- > next);} return dummy- > next;}}

The following solution uses the idea of mixed sorting, which is also a kind of divide-and-conquer method. The method is to divide the original linked list into two segments, and then call the recursive function for each segment. The left and right returned by suppose have been merged, and then the left and right are merged. The merging method can use any one of the previous Merge Two Sorted Lists solutions. Recursive writing is used here, while iterative writing is used in the first solution of this problem. See the code as follows:

Solution 3:

Class Solution {public: ListNode* mergeKLists (vector& lists) {return helper (lists, 0, (int) lists.size ()-1);} ListNode* helper (vector& lists, int start, int end) {if (start > end) return NULL; if (start = = end) return lists [start]; int mid = start + (end-start) / 2; ListNode* left = helper (lists, start, mid) ListNode* right = helper (lists, mid + 1, end); return mergeTwoLists (left, right);} ListNode* mergeTwoLists (ListNode* L1, ListNode* L2) {if (! L1) return L2; if (! L2) return L1; if (L1-> val

< l2->

Val) {L1-> next = mergeTwoLists (L1-> next, L2); return L1;} else {12-> next = mergeTwoLists (L1, 12-> next); return L2;}

The following solution uses the idea of counting and sorting, the idea is to record the maximum and minimum values of all node values, and then record the number of times each node value appears, so that when traversing from the minimum value to the maximum value, all the node values will be passed sequentially, and the corresponding number of nodes will be established according to the number of times they appear. However, there is a special point to pay attention to in this solution, that is, the merged linked list nodes are all re-established. In some cases, if you cannot create new nodes, but can only exchange or re-link nodes, then this solution cannot be used. Fortunately, there is no such limitation in this question, and you can pass OJ perfectly. See the code as follows:

Solution 4:

Class Solution {public: ListNode* mergeKLists (vector& lists) {ListNode* dummy = new ListNode (- 1), * cur = dummy; unordered_map m; int mx = INT_MIN, mn = INT_MAX; for (auto node: lists) {ListNode* t = node; while (t) {mx = max (mx, t-> val) Mn = min (mn, t-> val); + m [t-> val]; t = t-> next;}} for (int I = mn; i next = new ListNode (I); cur = cur- > next;}} return dummy- > next;}} This is the end of the content of "how C++ merges k ordered linked lists". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.