The second week Merge k Sorted Lists

Merge k Sorted 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

题解

分: When the linked list to be sorted is greater than 2, the linked list is divided into left and right parts. If the number of linked lists is one, Copy the linked list and return Governing: Sorting two sorted linked lists, returning a sorted linked list containing two linked list elements

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return NULL;
        return _mergeKlists(lists, 0, lists.size() - 1);
    }

    ListNode* _mergeKlists(vector<ListNode*>& lists, int left, int right) {
        ListNode* newList = new ListNode(0);
        ListNode* cur = newList;

        if (left == right) {
            ListNode* p = lists[left];
            while (p != NULL) {
                cur->next = new ListNode(p->val);
                p = p->next;
                cur = cur->next;
            }
        }
        else {
            int mid = (left + right) / 2;
            ListNode* l = _mergeKlists(lists, left, mid);
            ListNode* r = _mergeKlists(lists, mid + 1, right);
            while (l != NULL && r != NULL) {
                if (l->val < r->val) {
                    cur->next = l;
                    l = l->next;
                }
                else {
                    cur->next = r;
                    r = r->next;
                }
                cur = cur->next;
            }
            if (l == NULL) {
                cur->next = r;
            }
            else {
                cur->next = l;
            }
        }

        cur = newList->next;
        delete newList;
        return cur;
    }
};

分析

Algorithm divides multiple sorted linked lists into two parts, and finally two The sorted linked list is merged into a sorted linked list, let N be the total number of nodes, and k is the total number of linked lists. Then the algorithm will divide and divide by log2(k) times. The time complexity of each merged list is O(N), so the total time is O(log2(k) * N).