Merge K Sorted Lists

Merge k Sorted Lists

`Heap`

Description

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

Example

Example 1

``````Input:   [2->4->null, null, -1->null]
Output:  -1->2->4->null``````

Example 2

``````Input: [2->6->null, 5->null, 7->null]
Output: 2->5->6->7->null``````

Example 3

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

题解思路

1. 使用merge sort中的二分的思维，将包含k个链表的列表逐次分成两个部分，再逐次对两个链表合并，这样就有 log(k)次合并过程，每次均使用merge two sorted lists的算法。时间复杂度O(nlog(k))，不需要额外空间，因此空间复杂度O(1)。

2. 使用Priority Queues。这样保持每次取出的节点中是当前最小的，依次加入新的链表，从而得到合并的结果。时间复杂度O(nlogk)，空间复杂度O(k) 是PriorityQueue的空间。

源代码

• Divide and Conquer

``````/**
* Definition for ListNode.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int val) {
*         this.val = val;
*         this.next = null;
*     }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode lastNode = dummy;

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
lastNode.next = l1;
l1 = l1.next;
} else {
lastNode.next = l2;
l2 = l2.next;
}
lastNode = lastNode.next;
}

if (l1 != null) {
lastNode.next = l1;
} else {
lastNode.next = l2;
}

return dummy.next;
}
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKListsNaive(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
if (lists.size() == 1) {
return lists.get(0);
}

int listSize = lists.size();

ListNode base = lists.get(0);

for (int i = 1; i < listSize; i++) {
base = mergeTwoLists(base, lists.get(i));
}
return base;
}
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
if (lists.size() == 0) {
return null;
}
if (lists.size() == 1) {
return lists.get(0);
}
if (lists.size() == 2) {
return mergeTwoLists(lists.get(0), lists.get(1));
}
return mergeTwoLists(
mergeKLists(lists.subList(0, lists.size()/2)),
mergeKLists(lists.subList(lists.size()/2, lists.size()))
);
}
}``````
• Divide & Conquer Another implementation

``````public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
if (lists.size() == 0) {
return null;
}
return mergeHelper(lists, 0, lists.size() - 1);
}

private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
if (start == end) {
return lists.get(start);
}

int mid = start + (end - start) / 2;
ListNode left = mergeHelper(lists, start, mid);
ListNode right = mergeHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}

private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
tail = list1;
list1 = list1.next;
} else {
tail.next = list2;
tail = list2;
list2 = list2.next;
}
}
if (list1 != null) {
tail.next = list1;
} else {
tail.next = list2;
}

return dummy.next;
}
}``````
• Heap*

``````public class Solution {
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
public int compare(ListNode left, ListNode right) {
if (left == null) {
return 1;
} else if (right == null) {
return -1;
}
return left.val - right.val;
}
};

public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}

Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null) {
}
}

ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {