leetcode23-合并K个排序链表

原题

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

示例:

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

解法

思想

逐一比较或两两合并(分治)。

代码

逐一比较: 时间复杂度O(nm)(n为链表个数,m为链表最大长度)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int min = -1;
        int leftCount = lists.length;
        while(leftCount>0){
            for(int i = 0;i<leftCount;i++){
                if(lists[i]!=null&&(min==-1||lists[i].val<lists[min].val)) min = i;
            }
            if(min == -1){
                leftCount--;
                break;
            }
            ListNode node = lists[min];
            if(lists[min].next==null){
                lists[min]=lists[leftCount-1];
                leftCount--;
            }else lists[min] = lists[min].next;
            cur.next = node;
            cur = cur.next;
            min = -1;
        }
        return head.next;
    }
}

两两合并:时间复杂度O(nm/2)(n为链表个数,m为链表最大长度)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        // 将n个链表以中间为对称,合并
        while(len>1) {
            for (int i=0; i<len/2; i++) {
                lists[i] = mergeTwoListsForK(lists[i], lists[len-1-i]);
            }
            len = (len+1)/2;
        }
        return lists[0];
    }

    private ListNode mergeTwoListsForK(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        } else if (l2 != null) {
            p.next = l2;
        }
        return head.next;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode23-%e5%90%88%e5%b9%b6k%e4%b8%aa%e6%8e%92%e5%ba%8f%e9%93%be%e8%a1%a8/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月4日
下一篇 2020年2月4日

相关推荐

  • leetcode38-外观数列

    原题 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作…

    算法 2020年4月30日
    0290
  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树…

    算法 2020年1月16日
    0100
  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"…

    算法 2019年12月22日
    0130
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    080
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0150
  • leetcode34--在排序数组中查找元素的第一个和最后一个位置

    原题 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数…

    算法 2020年1月3日
    0160
  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0200
  • leetcode287-寻找重复数

    原题 给定一个包含 n + 1 个整数的数组 nums ,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 …

    2020年1月7日
    0100
  • leetcode1114-按序打印

    原题 我们提供了一个类: public class Foo {   public void one() { print("one"); }   public void two() …

    算法 2020年2月1日
    0140
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0210

发表回复

登录后才能评论