合并k个排序链表（leetcode_23）

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

我开始没看到排序这个条件，然后用的是堆排序，不过也不是真的堆，准确来说是仿照建堆的过程，将输入的数组按照左小右大的过程，建立一个排序二叉树，最后递归建立我们需要的序列，不过我实现起来有点麻烦，重复访问次数有点多，最后总体时间有点长，但是我觉得就单说时间复杂度上来说，应该我的时间更少，毕竟比较次数更少

struct ListNode

{

    int val;

    ListNode *next;

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

};



struct Tree

{

    int val;

    Tree *left;

    Tree *right;

    Tree(int x) : val(x), left(NULL), right(NULL) {}

};



class Solution

{

public:

    ListNode *mergeKLists(vector<ListNode *> &lists)

    {

        if (lists.empty())

            return NULL;



        Tree *root = new Tree(0);



        int size = lists.size();



        for (int i = 0; i < size; ++i)

        {

            struct ListNode *tmpNode = lists[i];

            while (tmpNode != NULL)

            {

                insertNode(root, tmpNode);

                tmpNode = tmpNode->next;

            }

        }



        ListNode *result = new ListNode(0);

        constructNode(root, result);



        return result->next->next;

    }



    void insertNode(Tree *root, ListNode *node)

    {

        if (node->val < root->val)

        {

            if (root->left == NULL)

            {

                root->left = new Tree(node->val);

                return;

            }

            insertNode(root->left, node);

        }

        else

        {

            if (root->right == NULL)

            {

                root->right = new Tree(node->val);

                return;

            }

            insertNode(root->right, node);

        }

    }



    void constructNode(Tree *root, ListNode *node)

    {

        if (root == NULL)

            return;

        constructNode(root->left, node);

        ListNode *tmp = node;

        while (tmp->next != NULL)

        {

            tmp = tmp->next;

        }

        tmp->next = new ListNode(root->val);



        constructNode(root->right, node);

    }

};

我看大神写的代码是用递归插入排序写的，就类似归并排序，但是只不过最底层不是只有两个数组比较，而是每个链表元素进行比较，使用的是插入排序，返回两个数组排序后的一个数组。但是我个人觉得这个进行排序的时候很麻烦，时间上来说不优化，只不过是构建最终结果的时候很方便，我自己的那个是最后构建的时候不知道最后一个元素在哪，然后遍历元素，所以这样每次遍历最后结果就慢了。

class Solution {

public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {

        return helper(lists,0,lists.size()-1);

    }

    ListNode* helper(vector<ListNode*>& lists, int left, int right) {

        if (left>right) return nullptr;

        if (left==right) return lists[left];

        int mid=(left+right)/2;

        ListNode* p1=helper(lists, left, mid);

        ListNode* p2=helper(lists, mid+1, right);

        ListNode q(-1);

        ListNode* tmp=&q;

        while (p1 and p2) {

            if (p1->val<p2->val) {

                tmp->next=p1;

                tmp=p1;

                p1=p1->next;

            } else {

                tmp->next=p2;

                tmp=p2;

                p2=p2->next;

            }

        }

        if (p1) tmp->next=p1;

        if (p2) tmp->next=p2;

        return q.next;

    }

};