# 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```

## 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;
}

}

@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 条评论

——老子

——老子

• ### 腾讯开源框架TarsCpp-rpc设计分析-client（一）

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

——老子

——老子

——老子

• ### 冲上云霄，Dubbo Go！

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

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

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

——老子

——老子

AmazonSDE II