Topic Description (Difficult Difficulty)
A combination of k ordered lists.
Let’s call N the total length of the list, and in the worst case, k lists of equal length are all N.
Solution 1 brute force cracking
Simple and crude, iterate through the list, store the numbers in an array, then use quicksort, and finally store the sorted array in a linked list.
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> l = new ArrayList<Integer>();
// Save to array
for (ListNode ln : lists) {
while(ln ! =null) { l.add(ln.val); ln = ln.next; }}// Array sort
Collections.sort(l);
// Save to the linked list
ListNode head = new ListNode(0);
ListNode h = head;
for (int i : l) {
ListNode t = new ListNode(i);
h.next = t;
h = h.next;
}
h.next = null;
return head.next;
}
Copy the codeTime complexity: assuming N is the number of all the numbers stored in the array is O (N), sorting if using quicksort
Spatial complexity: A new linked list, O (N) is created.
Solution two column by column comparison
We can compare them column by column, and store the smallest one in a new list.
public ListNode mergeKLists(ListNode[] lists) {
int min_index = 0;
ListNode head = new ListNode(0);
ListNode h = head;
while (true) {
boolean isBreak = true;// Flag whether all lists have been traversed
int min = Integer.MAX_VALUE;
for (int i = 0; i < lists.length; i++) {
if(lists[i] ! =null) {
// find the minimum subscript
if (lists[i].val < min) {
min_index = i;
min = lists[i].val;
}
// there is a linked list that is not empty, the flag is changed to false
isBreak = false; }}if (isBreak) {
break;
}
// Add to the new list
ListNode a = new ListNode(lists[min_index].val);
h.next = a;
h = h.next;
// Move the list back one element
lists[min_index] = lists[min_index].next;
}
h.next = null;
return head.next;
}
Copy the codeTime complexity: Assuming the longest list length is N, then the while loop will loop n times. If there are k lists in the list, the for loop executes k times, so the time complexity is O (kn).
Space complexity: N represents the length of the final linked list, then O (N).
In fact, we don’t need to create a new list to keep, we just need to change the direction of the smallest node.
public ListNode mergeKLists(ListNode[] lists) {
int min_index = 0;
ListNode head = new ListNode(0);
ListNode h = head;
while (true) {
boolean isBreak = true;
int min = Integer.MAX_VALUE;
for (int i = 0; i < lists.length; i++) {
if(lists[i] ! =null) {
if (lists[i].val < min) {
min_index = i;
min = lists[i].val;
}
isBreak = false; }}if (isBreak) {
break;
}
// Get the smallest node
h.next = lists[min_index];
h = h.next;
lists[min_index] = lists[min_index].next;
}
h.next = null;
return head.next;
}
Copy the codeTime complexity: Assuming the longest list length is N, then the while loop will loop n times. If there are k lists in the list, the for loop executes k times, so the time complexity is O (kn).
Space complexity: O (1).
Solution three priority queue
In solution two, we take the smallest one every time, add a new one, O (1), and find the smallest one, O (k). We could have used a priority queue.
We’re going to define the number of priorities as small as possible, and if we implement the priority queue with the heap, so that every time we find the smallest, we don’t need order k, but order log of k, and of course, if we add new words, instead of order 1, we need order log of k. You can see here and here.
public ListNode mergeKLists(ListNode[] lists) {
// Define the priority queue comparator
Comparator<ListNode> cmp;
cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
// TODO Auto-generated method stub
returno1.val-o2.val; }};// Create a queue
Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
for(ListNode l : lists){
if(l! =null){
q.add(l);
}
}
ListNode head = new ListNode(0);
ListNode point = head;
while(! q.isEmpty()){/ / out of the queue
point.next = q.poll();
point = point.next;
// Check whether the current list is empty. If not, add new elements to the list
ListNode next = point.next;
if(next! =null){ q.add(next); }}return head.next;
}
Copy the codeTime complexity: If there are N nodes in total, log (k) is required for each node to enter and exit the queue, and the time complexity of all nodes is O (N log (k)).
Space complexity: Priority queues need O (k) complexity.
Solution number four combines two by two
Using the previous algorithm to merge two lists, we directly merge the 0 list with the 1 list, merge the newly generated list with the 2 list, merge the newly generated list with the 3 list… Until it’s all merged.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h = new ListNode(0);
ListNode ans=h;
while(l1 ! =null&& l2 ! =null) {
if (l1.val < l2.val) {
h.next = l1;
h = h.next;
l1 = l1.next;
} else{ h.next = l2; h = h.next; l2 = l2.next; }}if(l1==null){
h.next=l2;
}
if(l2==null){
h.next=l1;
}
return ans.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==1) {return lists[0];
}
if(lists.length==0) {return null;
}
ListNode head = mergeTwoLists(lists[0],lists[1]);
for (int i = 2; i < lists.length; i++) {
head = mergeTwoLists(head,lists[i]);
}
return head;
}
Copy the codeTime complexity: Let’s say there are k lists of the same length, and the total length of the list is N, then the first merge will be N/ K and N/k, the second merge will be 2 * N/k and N/k, and the third merge will be 3 * N/k and N/k, and there will be N minus 1 merge, The time for each merge is order n, so the total time is zero
Space complexity: O (1).
# Solution 5 p2-p2 merge optimization
Again, assuming k lists, the merge process is optimized so that only log (k) is merged.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h = new ListNode(0);
ListNode ans=h;
while(l1 ! =null&& l2 ! =null) {
if (l1.val < l2.val) {
h.next = l1;
h = h.next;
l1 = l1.next;
} else{ h.next = l2; h = h.next; l2 = l2.next; }}if(l1==null){
h.next=l2;
}
if(l2==null){
h.next=l1;
}
return ans.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) {return null;
}
int interval = 1;
while(interval<lists.length){
System.out.println(lists.length);
for (int i = 0; i + interval< lists.length; i=i+interval*2) {
lists[i]=mergeTwoLists(lists[i],lists[i+interval]);
}
interval*=2;
}
return lists[0];
}
Copy the codeTime complexity: Assuming that the length of each list is N, then the time complexity is
Space complexity: O (1).
The total
I was impressed with the use of priority queues. In addition, for the merge of two linked lists, we reduced the time complexity by simply changing the merge method.
See Leetcode.Wang for more details on popular problems.