题解 | #合并k个已排序的链表#

// https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/

#include <vector>
class List {
    ListNode vHead;

  public:
    List& operator=(const List&) = default;
    List(ListNode* p) : vHead(0) {
        vHead.next = p;
    }
    List() : List(nullptr) {}

    // 返回链表头
    ListNode* GetHead() const {
        return vHead.next;
    }
    bool IsEmpty() const {
        return vHead.next == nullptr;
    }
    int Front() const {
        return vHead.next->val;
    }

    // 将 x 插入到链表头，返回 x -> next
    ListNode* PushFront(ListNode* x) {
        ListNode* tmp = x->next;
        x->next = vHead.next;
        vHead.next = x;
        return tmp;
    }
    // 弹出第一个元素
    ListNode* PopFront() {
        if (IsEmpty()) return nullptr;
        auto ret = vHead.next;
        vHead.next = ret->next;
        ret->next = nullptr;
        return ret;
    }

    // 反转链表
    void Reverse() {
        List tmp;
        while (vHead.next != nullptr) vHead.next = tmp.PushFront(vHead.next);
        *this = tmp;
    }

    // 将从第 n 个节点开始的子链表分割，并返回
    List Split(int n) {
        ListNode* p1 = &vHead;
        for (int i = 0; i < n - 1; ++i) {
            if (p1 == nullptr) return {};  // 什么都不分割
            p1 = p1->next;
        }
        List ret(p1->next);
        p1->next = nullptr;
        return ret;
    }

    // 将分割并返回最后 n 个节点。如果链表少于 n 个节点，那么返回 null
    List SplitR(int n) {
        if (n <= 0) return nullptr;  // 非法情况
        ListNode* p2 = vHead.next;
        for (int i = 1; i < n &&
                p2 != nullptr; ++i) {  // 将快指针移至第 n 个元素处
            p2 = p2->next;
        }
        if (p2 == nullptr) return nullptr;           // 少于 n 个元素
        if (p2->next == nullptr) return vHead.next;  // 正好 n 个元素
        ListNode* p1 = vHead.next;
        p2 = p2->next->next;  // 保证 p1 到 p2 之间有 n 个元素（不算 p1, p2）
        while (p2 != nullptr) {
            p1 = p1->next;
            p2 = p2->next;
        }
        p2 = p1->next;  // 返回值
        p1->next = nullptr;
        return p2;
    }
    // 将两个链表合并
    void Merge(const List& p) {
        auto tail = &vHead;
        while (tail->next != nullptr) {
            tail = tail->next;
        }
        tail->next = p.GetHead();
    }
    void oddEvenReorder() {
        List l1, l2;
        while (!IsEmpty()) {
            l1.PushFront(this->PopFront());
            if (!IsEmpty()) l2.PushFront(this->PopFront());
        }
        while (!l2.IsEmpty()) this->PushFront(l2.PopFront());
        while (!l1.IsEmpty()) this->PushFront(l1.PopFront());
    }

    // 将两个有序链表合并。首先保证这两个链表是有序的
    void MergeInorder(List& l2) {
        if (l2.IsEmpty()) return;
        if (IsEmpty()) {
            *this = l2;
            return;
        }
        auto& l1 = *this;
        List ret;
        while (!l1.IsEmpty() && !l2.IsEmpty()) {
            if (l1.Front() < l2.Front())
                ret.PushFront(l1.PopFront());
            else
                ret.PushFront(l2.PopFront());
        }
        while (!l1.IsEmpty()) ret.PushFront(l1.PopFront());
        while (!l2.IsEmpty()) ret.PushFront(l2.PopFront());
        ret.Reverse();
        *this = ret;
    }

    // 均分链表，返回后半段
    List Div() {
        if (vHead.next == nullptr) return {}; // 无元素
        if (vHead.next->next == nullptr) return {}; // 1 个元素
        ListNode* p1 = &vHead;
        ListNode* p2 = p1;
        while (p2 != nullptr && p2->next != nullptr) {
            p1 = p1->next;        // p1 每次走一步
            p2 = p2->next->next;  // p2 每次走两步
        }
        ListNode* ret = p1->next;
        p1->next = nullptr;
        return ret;
    }
    // 归并排序
    void Sort() {
        if (IsEmpty()) return;
        if (vHead.next->next == nullptr) return; // 1 个元素
        List& l1 = *this;
        List l2 = l1.Div();
        l1.Sort();
        l2.Sort();
        l1.MergeInorder(l2);
    }

    // 是否是回文串
    bool IsPail() {
        if (IsEmpty()) return true;
        if (vHead.next->next == nullptr) return true; // 1 个元素
        List& l1 = *this;
        List l2 = l1.Div();
        l2.Reverse();
        auto p1 = l1.GetHead();
        auto p2 = l2.GetHead();
        bool isPail = true;
        while (p1 != nullptr && p2 != nullptr) {
            if (!isPail) break;
            if (p1->val != p2->val) isPail = false;
            p1 = p1->next;
            p2 = p2->next;
        }
        l2.Reverse();
        l1.Merge(l2);
        if (!isPail) return false;
        return true;
    }

    ListNode* EntryOfLoop() const {
        if (vHead.next == nullptr) return nullptr;
        auto p1 = vHead.next;
        auto p2 = p1;
        bool hasCycle = false;
        while (p2 != nullptr && p2->next != nullptr) {
            p1 = p1->next;        // p1 每次走一步
            p2 = p2->next->next;  // p2 每次走两步
            if (p1 == p2) {       // 相遇则有环
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) return nullptr;
        // 找环的入口
        p2 = vHead.next;
        while (p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }

    ListNode* FindFirstCommonNode(const List& l2) const {
        const List& l1 = *this;
        auto p1 = l1.vHead.next, p2 = l2.vHead.next;
        while (p1 != p2) {
            if (p1 == nullptr)
                p1 = l2.vHead.next;
            else
                p1 = p1->next;
            if (p2 == nullptr)
                p2 = l1.vHead.next;
            else
                p2 = p2->next;
        }
        return p1;
    }
    // 删除 p 的下一个节点
    ListNode* RemoveNextOf(ListNode* p) {
        auto ret = p->next;
        p->next = p->next->next;
        return ret;
    }

    void Unique() {
        if (vHead.next == nullptr) return; // 0 个元素
        if (vHead.next->next == nullptr) return; // 1 个元素
        ListNode* p = vHead.next;
        while (p->next != nullptr) {
            if (p->val == p->next->val) {
                RemoveNextOf(p);
            } else {
                p = p->next;
            }
        }
    }

    void deleteDuplicates() {
        if (vHead.next == nullptr) return; // 0 个元素
        if (vHead.next->next == nullptr) return; // 1 个元素
        ListNode* pre = &vHead;
        ListNode* p = vHead.next;
        while (p != nullptr && p->next != nullptr) {
            if (p->val != p->next->val) { // 若不相等
                pre = p;
                p = p->next;
            } else { // 相等
                // 删除与 p 相同的所有元素
                while (p->next != nullptr && p->val == p->next->val) RemoveNextOf(p);
                RemoveNextOf(pre); // 注意删除 p
                p = pre->next; // 更新 p
            }
        }
    }
    // 合并多个有序链表
    static List mergeListsInorder(vector<List>& lists) {
        List ret;
        // 删除空链表
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i].IsEmpty()) { // 将当前链表交换到容器尾部
                swap(lists[i], lists.back());
                lists.pop_back();
                --i;
            }
        }

        while (!lists.empty()) {
            int ans = 0; // 选择最小的节点放入
            for (int i = 0; i < lists.size(); ++i) {
                if (lists[i].Front() < lists[ans].Front()) {
                    ans = i;
                }
            }
            ret.PushFront(lists[ans].PopFront());
            if (lists[ans].IsEmpty()) {
                swap(lists[ans], lists.back());
                lists.pop_back();
            }
        }
        ret.Reverse();
        return ret;
    }
};


class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        vector<List> tmp;
        for (auto p : lists) tmp.push_back(p);
        return List::mergeListsInorder(tmp).GetHead();
    }
};