• [x] ### Divide and Conquer
• [x] ### Better PriorityQueue

better way: priority queue

also should know how to divide and conquer but you forget everything????!

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

This creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

Merge K Sorted Lists

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

Given lists:

[ 2->4->null,

null,

-1->null ],

return -1->2->4->null.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

    }
}

Divide and Conquer

time complexity O(nlogk) k is the number of list in lists divide the total number of lists into two part every time (er fen)

then merge needs time O(n)

space O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

// first divide and conquer

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return sort(lists, 0 , lists.length - 1);
    }
    public ListNode sort(ListNode[] lists, int start, int end) {
        if (start >= end) {
            return lists[start];
        }
        int mid = (end - start) / 2 + start;
        ListNode left = sort(lists, start,mid);
        ListNode right = sort(lists, mid + 1, end);
        return merge(left, right);
    }
    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        }else{
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}

Priority Queue !!!!!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> pqueue = new PriorityQueue<>(lists.length, (a, b) -> a.val-b.val);
        ListNode dummy = new ListNode(0);
        ListNode curt = dummy;
        for (ListNode list : lists) {
            if (list != null) {
                pqueue.offer(list);
            }
        }
        while (!pqueue.isEmpty()) {
            curt.next = pqueue.poll(); // 0 -> 1
            curt = curt.next;
            if (curt.next != null) {
                pqueue.offer(curt.next);
            }

        }
        return dummy.next;
    }
}