admin管理员组

文章数量:1027609

链表系列一＞合并 k 个升序链表

题目：

链接: link

这里是引用

方法一解析：

这里是引用

代码：

代码语言：javascript代码运行次数：0运行复制
public ListNode mergeKLists(ListNode[] lists) {
        //建立小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)-> v1.val - v2.val);

        //把所有头节点放入小根堆中
        for(ListNode l : lists){
            if(l != null){
                heap.offer(l);
            }
        }

        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(!heap.isEmpty()){
            ListNode t = he

            prev.next = t;
            prev.next = t;
            prev = t;
            if(t.next != null)
                heap.offer(t.next);
        }

        return ret.next;
    }

方法二解析：

这里是引用

代码：

代码语言：javascript代码运行次数：0运行复制
//递归写法:
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int left, int right){
        if(left > right)
            return null;
        if(left == right)
            return lists[left];    

        //1.平分数组    
        int mid = (left + right) / 2;
        //[left,mid][mid+1,right]

        //2.递归处理
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        //3.合并两个有序链表
       return megeToList(l1,l2);
    }

    private ListNode megeToList(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        ListNode cur1 = l1, cur2 = l2;

        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) prev.next = cur1;
        if(cur2 != null) prev.next = cur2;

        return ret.next;
    }
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-05-01，如有侵权请联系 cloudcommunity@tencent 删除return递归链表数组null

链表系列一＞合并 k 个升序链表

题目：

链接: link

这里是引用

方法一解析：

这里是引用

代码：

代码语言：javascript代码运行次数：0运行复制
public ListNode mergeKLists(ListNode[] lists) {
        //建立小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)-> v1.val - v2.val);

        //把所有头节点放入小根堆中
        for(ListNode l : lists){
            if(l != null){
                heap.offer(l);
            }
        }

        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(!heap.isEmpty()){
            ListNode t = he

            prev.next = t;
            prev.next = t;
            prev = t;
            if(t.next != null)
                heap.offer(t.next);
        }

        return ret.next;
    }

方法二解析：

这里是引用

代码：

代码语言：javascript代码运行次数：0运行复制
//递归写法:
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int left, int right){
        if(left > right)
            return null;
        if(left == right)
            return lists[left];    

        //1.平分数组    
        int mid = (left + right) / 2;
        //[left,mid][mid+1,right]

        //2.递归处理
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        //3.合并两个有序链表
       return megeToList(l1,l2);
    }

    private ListNode megeToList(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        ListNode cur1 = l1, cur2 = l2;

        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) prev.next = cur1;
        if(cur2 != null) prev.next = cur2;

        return ret.next;
    }
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-05-01，如有侵权请联系 cloudcommunity@tencent 删除return递归链表数组null

本文标签： 链表系列一＞合并 k 个升序链表

版权声明：本文标题：链表系列一＞合并 k 个升序链表 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747422079a2165587.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。