题解 | #合并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* mergeKLists(vector<ListNode*>& lists) {
        queue<ListNode*> que;
        int n = lists.size();
        if (!n) return nullptr;
        bool flag = true;
        while (flag) {
            flag = false;
            int idx = 0;
            for (int i = 0; i < n; ++i) {
                if (lists[i] != nullptr && !flag) {
                    flag = true;
                    idx = i;
                    continue;
                }
                if (lists[i] != nullptr) {
                    idx = lists[i]->val < lists[idx]->val ? i : idx;
                }
            }
            if (!flag) break;
            que.push(lists[idx]);
            lists[idx] = lists[idx]->next;
        }
        if (que.empty()) return nullptr;;
        ListNode* cur = que.front();
        que.pop();
        ListNode* first = new ListNode(0);
        first->next = cur;
        while (!que.empty()) {
            ListNode* next = que.front();
            que.pop();
            cur->next = next;
            cur = next;
        }
        return first->next;
        // write code here
    }
};

全部评论

相关推荐

07-04 16:00
门头沟学院 Java
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务