专栏首页dylanliuLeetCode23-Merge k Sorted Lists

LeetCode23-Merge k Sorted Lists

Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Mind path

多个有序node如果一次取一个需要循环一遍,这样每个都需要重复比较很多遍,借鉴mergeSort,将list分成两部分分别merge,递归merge一次只merge两个node,可以大大减少元素的比较次数。

由于每个元素需要比较log(k)次,所以时间复杂度应该是(size-of-all-elements)*log(n)

Solution

package com.dylan.leetcode;

import org.junit.Assert;
import org.junit.Test;

/**
 * Created by liufengquan on 2018/8/1.
 */
public class MergeKSortedLists {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        return merge(lists, 0, lists.length);
    }

    private ListNode merge(ListNode[] nodes, int left, int right) {
        if ((right - left) == 1) {
            return nodes[left];
        }
        if ((right - left) == 2) {
            //merge
            return merge(nodes[left], nodes[left + 1]);
        }
        int middle = left + (right - left) / 2;
        return merge(merge(nodes, left, middle), merge(nodes, middle, right));
    }

    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode temp = new ListNode(0);
        ListNode head = temp;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                temp.next = node2;
                temp = temp.next;
                node2 = node2.next;
            }else {
                temp.next = node1;
                temp = temp.next;
                node1 = node1.next;
            }
        }
        if (node1 != null) {
            temp.next = node1;
        }
        if (node2 != null) {
            temp.next = node2;
        }

        return head.next;
    }

    @Test
    public void test() {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(4);
        node1.next.next = new ListNode(5);

        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(4);

        ListNode node3 = new ListNode(2);
        node3.next = new ListNode(6);

        ListNode[] nodes = new ListNode[]{node1, node2, node3};
        ListNode result = mergeKLists(nodes);

        Assert.assertEquals(1, result.val);
        result = result.next;
        Assert.assertEquals(1, result.val);
        result = result.next;
        Assert.assertEquals(2, result.val);
        result = result.next;
        Assert.assertEquals(3, result.val);
        result = result.next;
        Assert.assertEquals(4, result.val);
        result = result.next;
        Assert.assertEquals(4, result.val);
        result = result.next;
        Assert.assertEquals(5, result.val);
        result = result.next;
        Assert.assertEquals(6, result.val);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 | 每日一练(29)

    ——老子

    闫小林
  • 数据结构 | 每日一练(26)

    ——老子

    闫小林
  • 腾讯开源框架TarsCpp-rpc设计分析-client(一)

    Tars是腾讯开源的微服务平台,包含了一个高性能的rpc框架和服务治理平台,TarsCpp是其C++版本。对于以C++为主要开发语言,同时还想深入了解rpc和微...

    路小饭
  • 数据结构 | 每日一练(27)

    ——老子

    闫小林
  • 数据结构 | 每日一练(24)

    ——老子

    闫小林
  • 数据结构 | 每日一练(28)

    ——老子

    闫小林
  • 冲上云霄,Dubbo Go!

    5 月 21 日,经过一年多的孵化,Apache Dubbo 从 Apache 软件基金会毕业,成为 Apache 顶级项目。推荐:厉害了,Dubbo 正式毕业...

    Java技术栈
  • 做 Java 或者 C++ 开发都应该知道的 lsof 命令

    lsof 命令是 Linux 系统的扩展工具,它的含义是 list opened filedesciptor (列出已经打开的文件描述符),在 Linux 系统...

    范蠡
  • 数据结构 | 每日一练(32)

    ——老子

    闫小林
  • 数据结构 | 每日一练(33)

    ——老子

    闫小林

扫码关注云+社区

领取腾讯云代金券