23. 合并K个排序链表*

2019-04-20  本文已影响0人  薄荷糖的味道_fb40

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

示例:

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

思路:

用一个和lists一样大的指针数组存放每一行当前的最小值的地址,每次遍历这些最小值取最小加入新节点中,时间复杂度为O(k),k为总元素个数,空间复杂度为O(m),m为lists大小,具体实现如下。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> p(lists.size(),nullptr);
        ListNode* head=new ListNode(0);
        ListNode* ptr =head;
        int len=0;
        for(int i=0;i<lists.size();i++)
        {
            p[i]=lists[i];
        }
        do
        {
            ptr->next=minptr(p);
            ptr=ptr->next;
        }
         while(ptr);
        
        return head->next;
    }
    ListNode* minptr(vector<ListNode*>& p)
    {
        int min=INT_MAX;
        ListNode* res=nullptr;
        int index=-1;
        for(int i=0;i<p.size();i++)
        {
            if(p[i] && min>p[i]->val)
            {
                min=p[i]->val;
                res=p[i];
                index=i;
            }
        }
        if(index>=0)
        {
            p[index]=p[index]->next;
        }
        
        return res;
    }

};

mark一下,感觉还有很多快的解法。

上一篇 下一篇

猜你喜欢

热点阅读