Title Description (Difficulty)
Merge of k ordered chains.
We use N to represent the total length of the list. For the worst case scenario, k lists have the same length, all of which are n.
Solution - Violence
Simple and rough, iterate through all the lists, save the numbers in an array, sort them quickly, and save the sorted array in a 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 sorting Collections.sort(l); //Save to Chain 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; }
Time Complexity: Assume N is the number of all numbers, O (N) is stored in the array, O(Nlog_N)$is used for sorting fast, O (N) is stored in the chain table, so the largest one is $O(Nlog_N)$.
Spatial Complexity: A new chain table, O(N), is created.
Solution Two One Column One Column Comparison
We can compare columns by columns 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;//Whether the tag has traversed all the linked lists int min = Integer.MAX_VALUE; for (int i = 0; i < lists.length; i++) { if (lists[i] != null) { //Find Minimum Subscript if (lists[i].val < min) { min_index = i; min = lists[i].val; } //There is a list that is not empty, marker changed to false isBreak = false; } } if (isBreak) { break; } //Add to New Chain List ListNode a = new ListNode(lists[min_index].val); h.next = a; h = h.next; //Move an element back in the list lists[min_index] = lists[min_index].next; } h.next = null; return head.next; }
Time Complexity: Assuming the longest chain length is n, the while loop will loop n times.Assuming that there are k lists in the list of chains, the for loop executes K times, so the time complexity is O (kn).
Spatial Complexity: N represents the length of the final list, or O(N).
In fact, we don't need to create a new list to save, we just need to change the point of the smallest node we get.
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; } //The smallest node is coming h.next = lists[min_index]; h = h.next; lists[min_index] = lists[min_index].next; } h.next = null; return head.next; }
Time Complexity: Assuming the longest chain length is n, the while loop will loop n times.Assuming that there are k lists in the list of chains, the for loop executes K times, so the time complexity is O (kn).
Spatial complexity: O (1).
Solution Triple Priority Queue
In Solution 2, each time we take out a minimum, then add a new, O(1) complexity and find the minimum, O(k) complexity.We can use a preferred queue entirely.
We define the priority as the smaller the number, the higher the priority. If we use the heap to achieve the priority queue, then we no longer need O(k) for each minimum, but O(log(k)) for each search. Of course, if we add a new one, we no longer need O(1) but also O(log(k).You can see Here and Here.
public ListNode mergeKLists(ListNode[] lists) { //A comparator that defines a priority queue Comparator<ListNode> cmp; cmp = new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { // TODO Auto-generated method stub return o1.val-o2.val; } }; //Set up 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 Queue point.next = q.poll(); point = point.next; //Determine if the current list is empty or not, and queue new elements ListNode next = point.next; if(next!=null){ q.add(next); } } return head.next; }
Time Complexity: If there are N nodes in total, each node needs log(k) to be queued, and all time complexity is O(N log(k).
Spatial Complexity: Priority queues require O(k) complexity.
Solution Four Two Merge
utilize before The algorithm for merging two linked lists. We merge the first and the tenth linked lists directly, merge the newly generated and second linked lists, merge the newly generated and third linked lists... until the merge is complete.
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; }
Time Complexity: Assume that K chains have the same length, and the total length of the chains is N, then the first merge is N/k and N/k, the second merge is 2 * N/k and N/k, the third merge is 3 * N/k and N/k, and the total merge is n - 1, each time the time complexity is O (n), so the total time complexity is $O (\sum_{i=1}^{k-1} (i*\frac{N}{k}+\frac{N}{k})=O(kN)$, which separates the two items. N/k is actually a constant and the first is an equal difference column.
Spatial complexity: O (1).
Solution Five-Two-Two Combination Optimization
It is still assumed that there are k linked lists, and the merging process is optimized so that only log (k) merges are needed.
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]; }
Time Complexity: Assuming the length of each chain table is n, the time complexity is $O(\sum_{i=1}^{log_2k}n)=O(nlogk)$.
Spatial complexity: O (1).
total
I'm impressed with the use of the priority queue, and with the merging of the two-linked lists, we've reduced the time complexity a lot by simply changing the way we merge. That's wonderful!
More detailed explanation of popular topics leetcode.wang .