• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# LeetCode – Hard – 23. Merge k Sorted Lists

2周前 (01-13) 11次浏览

## Topic

• Divide and Conquer
• Heap

## Description

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

``````Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1-&gt;4-&gt;5,
1-&gt;3-&gt;4,
2-&gt;6
]
merging them into one sorted list:
1-&gt;1-&gt;2-&gt;3-&gt;4-&gt;4-&gt;5-&gt;6
``````

Example 2:

``````Input: lists = []
Output: []
``````

Example 3:

``````Input: lists = [[]]
Output: []
``````

Constraints:

• `k == lists.length`
• `0 &lt;= k &lt;= 10^4`
• `0 &lt;= lists[i].length &lt;= 500`
• `-10^4 &lt;= lists[i][j] &lt;= 10^4`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` won’t exceed `10^4`.

## Analysis

LeetCode 21. Merge Two Sorted Lists的延伸。

## Submission

``````import com.lun.util.SinglyLinkedList.ListNode;

public class MergeKSortedLists {

public ListNode mergeKLists(ListNode[] lists) {
ListNode result = null;
if (lists == null)
return result;

for (ListNode list : lists) {
result = mergeTwoList(result, list);
}

return result;
}

private ListNode mergeTwoList(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val &lt; l2.val) {
l1.next = mergeTwoList(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoList(l1, l2.next);
return l2;
}
}

}
``````

## Test

``````import static org.junit.Assert.*;

import org.junit.Test;

public class MergeKSortedListsTest {

@Test
public void test() {
MergeKSortedLists obj = new MergeKSortedLists();

ListNode[] lists1 = {ints2List(1, 4, 5), ints2List(1, 3, 4), ints2List(2, 6)};
ListNode expected1 = ints2List(1, 1, 2, 3, 4, 4, 5, 6);

assertTrue(areTwoListEqual(obj.mergeKLists(lists1), expected1));

ListNode[] list2 = null;
assertNull(obj.mergeKLists(list2));

ListNode[] list3 = {};
assertNull(obj.mergeKLists(list3));
}
}
``````
{{o.name}}

{{m.name}}