6b.LeetCode.23.Merge k Sorted Lists【K個排序鏈表歸併】

K個排序鏈表歸併【23】(hard)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


bool cmp(const ListNode *a, const ListNode *b) { return a->val < b->val; }

class Solution {
 public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *temp_head = new ListNode(-1);
        ListNode *pre = temp_head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                pre->next = l1;
                l1 = l1->next;
            } else {
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;
        }
        if (l1)
            pre->next = l1;

        if (l2)
            pre->next = l2;

        return temp_head->next;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // 方法二、分治法
        if (lists.size() == 0)  // list爲空, 返回NULL
            return NULL;

        if (lists.size() == 1)  // 只有一個lists, 直接返回頭指針
            return lists[0];

        if (lists.size() == 2)  // 兩個lists,呼叫兩個list merge函數
            return mergeTwoLists(lists[0], lists[1]);

        int mid = lists.size() / 2;
        // 拆分lists爲兩個子lists
        vector<ListNode *> sub1_lists;
        vector<ListNode *> sub2_lists;
        for (int i = 0; i < mid; i++) {
            sub1_lists.push_back(lists[i]);
        }
        for (int i = mid; i < lists.size(); i++) {
            sub2_lists.push_back(lists[i]);
        }
        ListNode *l1 = mergeKLists(sub1_lists);
        ListNode *l2 = mergeKLists(sub2_lists);
        return mergeTwoLists(l1, l2);  // 分治處理
    }

    // ListNode *mergeKLists(std::vector<ListNode *> &lists) {
    //     // 方法一、排序法
    //     vector<ListNode *> node_vec;
    //     for (int i = 0; i < lists.size(); i++) {
    //         // 遍歷k個鏈表, 節點新增到node_vec
    //         ListNode *head = lists[i];
    //         while (head) {
    //             node_vec.push_back(head);
    //             head = head->next;
    //         }
    //     }
    //     if (node_vec.size() == 0) {
    //         return NULL;
    //     }
    //     // 根據節點值,排序
    //     sort(node_vec.begin(), node_vec.end(), cmp);
    //     for (int i = 1; i <= node_vec.size(); i++) {
    //         // 鏈接新鏈表
    //         // 最後一個結點 i
    //         node_vec[i - 1]->next = node_vec[i];
    //     }
    //     // 尾結點置空
    //     node_vec[node_vec.size() - 1]->next = NULL;
    //     return node_vec[0];
    // }
};

int main() {
    ListNode a(1);
    ListNode b(4);
    ListNode c(6);
    ListNode d(0);
    ListNode e(5);
    ListNode f(7);
    ListNode g(2);
    ListNode h(3);
    a.next = &b;
    b.next = &c;
    d.next = &e;
    e.next = &f;
    g.next = &h;
    Solution solve;
    std::vector<ListNode *> lists;
    lists.push_back(&a);
    lists.push_back(&d);
    lists.push_back(&g);
    ListNode *head = solve.mergeKLists(lists);
    while (head) {
        cout << head->val << endl;
        head = head->next;
    }
    return 0;
}