23. Merge k Sorted Lists

归并 两两inplace merge O(nlogk) k是lists数 n是所有node数 O(1) space

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        def merge(a, b):
            tail = dummy = ListNode()
            while a and b:
                if a.val < b.val:
                    tail.next = a
                    a = a.next
                else:
                    tail.next = b
                    b = b.next
                tail = tail.next
            tail.next = a if a else b
            return dummy.next
        step, n = 1, len(lists)
        while step < n:
            for i in range(0, n, step << 1):
                if i + step >= n: break
                lists[i] = merge(lists[i], lists[i + step])
            step <<= 1
        return lists[0]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        auto merge = [](auto a, auto b) {
            ListNode dummy_head(0), *tail = &dummy_head;
            while (a && b) {
                if (a->val < b->val) {
                    tail->next = a;
                    a = a->next;
                } else {
                    tail->next = b;
                    b = b->next;
                }
                tail = tail->next;
            }
            tail->next = a ? a : b;
            return dummy_head.next;
        };
        for (int n = lists.size(), step = 1; step < n; step <<= 1) {
            for (int i = 0; i + step < n; i += (step << 1)) {
                lists[i] = merge(lists[i], lists[i + step]);
            }
        }
        return lists[0];
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        for (int n = lists.size(), step = 1; step < n; step <<= 1) {
            for (int i = 0; i + step < n; i += (step << 1)) {
                lists[i] = merge(lists[i], lists[i + step]);
            }
        }
        return lists[0];
    }

    ListNode *merge(ListNode *a, ListNode *b) {
        ListNode dummy_head(0), *tail = &dummy_head;
        while (a && b) {
            if (a->val < b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy_head.next;
    }
};

external sort O(nlogk) n is the number of all nodes, k is the number of linked lists

from queue import PriorityQueue
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
ListNode.__lt__ = lambda x, y: x.val < y.val # ListNode无法直接比较，用val替代也不行，必须重载__lt__
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put(l)
        tail = dummy = ListNode()
        while not q.empty():
            l = q.get()
            tail.next = l
            tail = l
            l = l.next
            if l:
                q.put(l)
        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const auto &a, const auto &b) { return a->val > b->val; };
        priority_queue<ListNode *, vector<ListNode *>, decltype(cmp)> q(cmp);
        for (auto l : lists) {
            if (l) {
                q.push(l);
            }
        }
        ListNode dummy_head(0), *tail = &dummy_head;
        while (!q.empty()) {
            auto l = q.top(); q.pop();
            tail->next = l;
            tail = l;
            l = l->next;
            if (l) {
                q.push(l);
            }
        }
        return dummy_head.next;
    }
};