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

合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

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

    ListNode* min(vector<ListNode*>& lists) {
        int min_num = 1001;
        int idx = -1;
        ListNode* temp = new ListNode(0);
        for (struct {vector<ListNode*>::iterator p; int i;} s = {lists.begin(), 0}; s.p
                != lists.end();
                ++(s.p), s.i++) {
            if ((*s.p)->val < min_num) {
                idx = s.i;
                min_num = (*s.p)->val;
            }
        }
        temp->val = lists[idx]->val;
        lists[idx] = lists[idx]->next;
        return temp;
    }


    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here

        lists.erase(std::remove(lists.begin(), lists.end(), nullptr), lists.end());

        int k = lists.size();
        if (k == 0)return nullptr;

        ListNode* res = nullptr;
        ListNode* head = nullptr;


        ListNode* temp;
        while (lists.size()) {
            temp = min(lists);
            if (res == nullptr) {
                res = temp;
                head = res;
            } else {
                head->next = temp;
                head = head->next;
            }
            lists.erase(std::remove(lists.begin(), lists.end(), nullptr), lists.end());

        }


        return res;
    }
};

个人感觉这题并不是很难,因为没有要求空间复杂度,所以可以用一个新的链表去记录合并的排序结果。同时,与合并两个升序链表类似,用k个指针分别沿着k个链表移动,每次移动都选出一个最小值,链接到新链表的末尾。

事实上我上面的代码也没有用到(n)的空间复杂度,因为是在原来的k个链表空间上进行结点的重新链接。

耗费我很多时间的反而是在最开始和每次移动一个指针之后的检查k个链表并删除空链表,因为简单的在原有的链表向量中移除会导致向量的开始和结束位置发生变化,以及索引下标也会改变。最后还是使用<algorithm>库函数remove()来实现的。

全部评论

相关推荐

od现在都成这样了&nbsp;就业市场真是crazy
牛客473059135号:没事,我有个朋友是985本硕学计算机的,被华为卡目标院校了简历挂,不过不是od虽然人家拿到一堆别的offer了就挺搞笑的属于是……
点赞 评论 收藏
分享
待现的未见之事:起码第一句要把自己的优势说出来吧。比如什么xx本27届学生,随时到岗....
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
存一千万就可以进大厂实习
石圪节公社发型师:有存一千万的实力还实习个嘚,直接躺平
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务