This is the 27th day of my participation in the Genwen Challenge

Topic describes

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 code

Example 2:

Input: Lists = [] Output: []Copy the code

Example 3:

Input: Lists = [[]] Output: []Copy the code

Tip:

  • k= =lists.length
  • 0 < =k< =
    1 0 4 10 ^ 4
  • 0 < =lists[i].length< = 500

  • – 1 0 4 – 10 ^ 4     < =lists[i][j]< =
    1 0 4 10 ^ 4
  • lists[i] 按 ascendingarrangement
  • lists[i].lengthThe sum of does not exceed
    1 0 4 10 ^ 4

Their thinking

Before solving the problem of “merge K sorted lists”, let’s look at a simpler problem: how do you merge two ordered lists? Assume that list the length of a and b are n, how in O (n) O (n) O (n) time and O (1) O (1) O (1) space cost to complete the merger? This question often arises in interviews. In order to achieve the space cost of O(1)O(1)O(1), we aim to “adjust the next pointer to the linked list element in place to complete the merge”. Here are the steps and considerations for merging, which can be skipped for those familiar with the issue. This section recommends reading in conjunction with the code.

First we need a variable head to hold the head of the merged list. You can set head to a dummy head (the val attribute of head does not hold any value). This makes it easier to write the code.

We need a pointer tail to record the previous position of an insertion position, and two Pointers aPtr and bPtr to record the first of the unmerged parts of A and B. Notice that tail is not the next insertion position, and that the elements pointed to by aPtr and bPtr are in the “pending merge” state, meaning that they have not been merged into the final list. Of course you can give them other definitions, but the implementation will be different depending on the definition.

When neither aPtr nor bPtr is empty, val is used to know the smaller merge; If the aPtr is empty, merge the entire bPtr and subsequent elements; The same is true if bPtr is null.

When merging, adjust tail’s next attribute first, then move tail and *Ptr (aPtr or bPtr) later. Is there a sequence between tail and *Ptr? They are the same as which moves first and which moves last, and do not change the next pointer of any element

code

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if((! a) || (! b))return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1); }};Copy the code