Leetcode（23）-合并K个排序链表

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

示例:

输入:

[

  1->4->5,

  1->3->4,

  2->6

]

输出: 1->1->2->3->4->4->5->6

思路：k个链表是排好序的，那我们就可以依次，按顺序的比较每个链表的节点，将最小的依次放入一个新链表中。我的做法是动态申请一个指针数组，每个链表均由一个指针指向，然后就可以比较每个链表的值，直到每个链表为空。这里注意在遍历的时候要注意判断是否为空，否则就会出现一个链表为零，还在比较它的节点大小的情况，访问出错。

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

    {

        ListNode* newhead=new ListNode(0);

        ListNode* cur=newhead;

        int len=lists.size();

        if(len==0) return NULL;

        ListNode** p=new ListNode*[len];

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

        {

            p[i]=lists[i];

        }

        while(cur)

        {

            int pos=0;

            int min=INT_MAX;

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

            {

                if(p[i]&&min>p[i]->val  )//找到最小的节点，并记录链表的下标

                {

                    pos=i;

                    min=p[i]->val;

                }

            }

        if(p[pos])//不为空挂在后面，否则意味着全为空了，退出

        {

        cur->next=new ListNode(p[pos]->val);

        p[pos]=p[pos]->next;

        cur=cur->next;

        }

        else

        break;

        }

    return newhead->next;

}

其实我们可以用优先队列来完成找最小节点的任务。

struct cmp {

    bool operator() (const ListNode* a, const ListNode* b)

    {

        return a->val > b->val;

    }

};

class Solution {

public:

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

        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        ListNode *head = new ListNode(0);

        ListNode *curr = head;

        auto iter = lists.begin();

        for (; iter != lists.end(); iter++)

        {

            if (*iter != NULL)

            {

                heap.push(*iter);

            }

        }

        while (!heap.empty())

        {

            ListNode* minNode = heap.top();

            heap.pop();

            ListNode* tmp = new ListNode(minNode->val);

            curr->next = tmp;

            curr = curr->next;

            if (minNode->next != NULL)

            {

                heap.push(minNode->next);

            }

        }

        return head->next;

    }

};

巴特西

Leetcode（23）-合并K个排序链表

最新文章

热门文章