题解 | #牛群的合并# Java

牛群的合并

https://www.nowcoder.com/practice/d0cb24e1494e4f45a4b7d1a17db0daef

借助小根堆数据结构,每次选择最小的节点,如果最小的节点有下一个,就加进堆里面

  • 掌握一下PriorityQueue借助Comparator初始化的方法
public class Solution {

    public ListNode mergeKLists (ListNode[] lists) {
        if (lists.length == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode p1, ListNode p2) {
                return p1.val - p2.val;
            }
        });
        for (ListNode ln : lists) {
            if (ln != null ) pq.add(ln);
        }

        ListNode dummy = new ListNode(-1), cur = dummy;
        while (!pq.isEmpty()) {
            ListNode tmp = pq.poll();
            if (tmp.next != null) {
                pq.add(tmp.next);
            }
            cur.next = tmp;
            cur = cur.next;
        }

        return dummy.next;
    }
}

算法题刷刷刷 文章被收录于专栏

数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序

全部评论

相关推荐

测试糕手手:社会第一课,随便吹牛逼,直接说四个月,别老实。老实人只会被欺负
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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