I was thinking for long about when and how to explain the divide-and-conquer approach with proper example. The merge sort could be a good one but it’s on the one hand too basic and on the other hand there are enough examples that anyone can find them using any search engine. So I decide to use “merge k sorted list” as a variation to the merge sort for explaining the divide-and-conquer approach.
The description of the problem is simple and clear: Merge k sorted linked lists and return it as one sorted list. For example: the input list are “0→3→6→7→8”, “1→2→3→5→6→7” and “0→3→4→9”, the output should be “0→0→1→2→3→3→3→4→5→6→6→7→7→8→9”. The linked list is given as follows:
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
next = null;
}
}
By the way, I have implemented some helper methods and overrode the hashCode(), equals(), toString() methods for simplifying the unit tests. you can find this ListNode.java on my Github
To solve the merge k sorted list, we will reuse the “merge 2 sorted list” which is implemented using recursion with O(M+N) time complexity:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
Here is another solution without recursion, note that the “new ListNode(0)” is just a fake head, will at last be skipped at returning.
public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = new ListNode(0); // create a fake head
ListNode p = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 == null) {
p.next = l2;
} else {
p.next = l1;
}
return head.next; // skip the fake head
}
Before we solve the “merge k sorted list”, we want to explain briefly what is divide-and-conquer approach. As its name mentioned, it will divide a big problem into small problem set and then conquer them. It sounds like dynamic programming but the difference is, the DP reuses the last biggest subset solution to solve the next and bigger subset, such as we had discussed in the Generate Parentheses. But the divide-and-donquer will only solve the smallest sub problem or with another word solve the “atomic problem” and divide the original problem into as many as possible “atomic problems” and at last compose the result set together in one final result. Because of this feature, it can often be solved with recursion. Let’s see the code:
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())));
}
The “atomic problem” here is when lists size is 1 and 2, in this case we can simply reused the mergeTwoLists() method to solve the problem. When size>2, we can divide the input lists into sub lists until the sub lists are small enough that can be solved with the mergeTwoLists(). The time complexity is O(NLogN), in which N is the sum of the total elements in K lists.
In this article, I tried using simple expression to explain the problem and the difference between DP and DC approach, if any question or correction, don’t hesitate to leave your comment here or contact me using the contact form.
rekinyZ's Blog 