It should be similar to merge two sort arrays. So we merge two lists until one list is exhausted. Then splice the results with leftovers in either L1 or L2.
Code
public ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
// modifying the head so dummy node
ListNode dummy = new ListNode(0);
ListNode t1 = l1;
ListNode t2 = l2;
ListNode current = dummy;
// merge what they have first
while (t1 != null && t2 != null) {
if (t1.val < t2.val) {
current.next = t1;
current = current.next;
t1 = t1.next;
} else {
current.next = t2;
current = current.next;
t2 = t2.next;
}
}
// splice the rest
if (t1 != null) current.next = t1;
if (t2 != null) current.next = t2;
// return new head
return dummy.next;
}
Merge k sorted linked lists and return it as one sorted list.
The brute force approach is to use a reduction algorithm and reduce the problem to the base case mergeTwoSortedLists. The worst case [1,2,3,4,5],[6],[7],[8],[9] can produce O(N^2) time. The classic k-way merge algorithm can be implemented in three ways. Top-down approach with divide and conquer, BFS approach with a priority queue, and bottom-up approach by merging lists in groups.
Brute Force Reduction
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
if (lists.length == 1) return lists[0];
ListNode masterHead = lists[0];
for (int i = 1; i < lists.length; i++) {
masterHead = mergeTwoSortedLists(masterHead, lists[i]);
}
return masterHead;
}
The brute force received Time Limit Exceeded with a large input of single number lists.
Divide and Conquer
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
return mergeKSortedLists(lists, 0, lists.length - 1);
}
private ListNode mergeKSortedLists(ListNode[] lists, int start, int end) {
// base case
if (start == end) {
return lists[start];
}
// divide
int mid = (start + end) / 2;
// conquer
ListNode l1 = mergeKSortedLists(lists, start, mid);
ListNode l2 = mergeKSortedLists(lists, mid+1, end);
// merge
return mergeTwoSortedLists(l1, l2);
}
Bottom Up Merge
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
ListNode[] currentLayer = lists;
ListNode[] nextLayer;
ListNode tempMerge;
while (currentLayer.length > 1) {
// init the next layer
int halfLength = (currentLayer.length + 1) / 2; // +1 to get enough space
nextLayer = new ListNode[halfLength];
// merge in groups of two lists
for (int i = 0; i + 1 < currentLayer.length; i += 2) {
tempMerge = mergeTwoSortedLists(currentLayer[i], currentLayer[i+1]);
nextLayer[i/2] = tempMerge;
}
// add the leftover list if currentLen is odd
if (currentLayer.length % 2 == 1) {
nextLayer[halfLength - 1] = currentLayer[currentLayer.length - 1];
}
// move up to the next layer
currentLayer = nextLayer;
}
return currentLayer[0];
}
Priority Queue Search
Unlike the first two approaches in which we rely on an implicit binary tree structure (height of lg(k) b/c base case is merge2lists), the priority queue uses an explicit full binary tree - heap. We keep the heap fed going down the k lists.
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
final int K = lists.length;
// modify head so dummy
ListNode dummy = new ListNode(0);
// init priority queue
Comparator<ListNode> lnodeComp = new Comparator<ListNode>() {
public int compare(ListNode n1, ListNode n2) {
if (n1 == null) return 1;
if (n2 == null) return -1;
return n1.val - n2.val;
}
};
Queue<ListNode> minHeap = new PriorityQueue<>(K, lnodeComp);
for (int i = 0; i < K; i++) {
if (lists[i] != null)
minHeap.offer(lists[i]);
}
// priority queue search
ListNode travel = dummy;
while (!minHeap.isEmpty()) {
ListNode localMin = minHeap.poll();
travel.next = localMin;
travel = travel.next;
if (travel.next != null)
minHeap.offer(travel.next);
}
// return merged list
return dummy.next;
}
