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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */

    void insertLists(ListNode* pre, ListNode* node)
    {
        ListNode* next = pre->next;
        pre->next = node;
        node->next = next;
        return;
    }

    ListNode* deleteLists(ListNode* pre, ListNode* next)
    {
        ListNode* node = pre->next;
        pre->next = next;
        node->next = nullptr;
        return node;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        ListNode* dummyhead = nullptr;
        ListNode* node = nullptr;
        if(!lists.size())
            return nullptr;
        for(int i = 0; i < lists.size(); ++i)
        {
                ListNode* create_head = new ListNode(0);
                create_head->next = lists[i];
                lists[i] = create_head;
        }

        for(auto it : lists)
        {
            if(!dummyhead)
            {
                dummyhead = it;
                continue;
            }
            ListNode* chead = it;
            ListNode* temp = dummyhead;
            while(chead && chead->next)
            {
                node = deleteLists(chead, chead->next->next);
                while(temp && temp->next && node->val > temp->next->val)
                {
                    temp = temp->next;
                }
                insertLists(temp, node);
            }
        }

        return dummyhead->next;
    }
};

使用哨兵节点简化解题中对头尾节点的处理，链表为正排序链表，因此每次循环插入时不用回退，减少代码运行时间提高代码质量