package 链表;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * @author Huangyujun
 *
 */
public class _23_合并K个升序链表 {
    //暴力（一条一条添加进来的合并法）
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            ListNode ans = null;
            for (int i = 0; i < lists.length; ++i) {
                ans = mergeTwoLists(ans, lists[i]);
            }
            return ans;
        }
        public ListNode mergeTwoLists(ListNode a, ListNode b) {
            if (a == null || b == null) {
                return a != null ? a : b;
            }
            ListNode head = new ListNode(0);
            ListNode tail = head, aPtr = a, bPtr = b;
            while (aPtr != null && bPtr != null) {
                if (aPtr.val < bPtr.val) {
                    tail.next = aPtr;
                    aPtr = aPtr.next;
                } else {
                    tail.next = bPtr;
                    bPtr = bPtr.next;
                }
                tail = tail.next;
            }
            tail.next = (aPtr != null ? aPtr : bPtr);
            return head.next;
        }
    }
    //分治合并法
    class Solution2 {
        public ListNode mergeKLists(ListNode[] lists) {
            return merge(lists, 0, lists.length - 1);
        }
        // 通过定义一个范围进行判断（之前是通过lists 的长度进行判断，也行）
        public ListNode merge(ListNode[] lists, int l, int r) {
            if (l == r) {
                return lists[l];
            }
            if (l > r) {
                return null;
            }
            int mid = (l + r) >> 1;
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
        public ListNode mergeTwoLists(ListNode a, ListNode b) {
            if (a == null || b == null) {
                return a != null ? a : b;
            }
            ListNode head = new ListNode(0);
            ListNode tail = head, aPtr = a, bPtr = b;
            while (aPtr != null && bPtr != null) {
                if (aPtr.val < bPtr.val) {
                    tail.next = aPtr;
                    aPtr = aPtr.next;
                } else {
                    tail.next = bPtr;
                    bPtr = bPtr.next;
                }
                tail = tail.next;
            }
            tail.next = (aPtr != null ? aPtr : bPtr);
            return head.next;
        }
    }
    //优先队列法（就是小根堆（具体代码就是 PriorityQueue类(长度，比较器)）~从小到大排序： 每条 链表会依据链表头的大小顺序进行排序~ 链表头小的放入前面，大的放到后面（从小到大~ 内部自动排序哈哈哈））
    class Solution3 {
           public ListNode mergeKLists(ListNode[] lists) {
                if (lists == null || lists.length == 0) return null;
                PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
                     @Override
                    public int compare(ListNode o1, ListNode o2) {
                        if (o1.val < o2.val) return -1;
                        else if (o1.val == o2.val) return 0;
                        else return 1;
                    }
                });
                ListNode dummy = new ListNode(0);
                ListNode p = dummy;
                //根据每条链表的头的值，从小到大排序，放入每条链表于queue 中
                for (ListNode node : lists) {
                    if (node != null) queue.add(node);
                }
                // 每次都弹出链表头最小的链表（然后取走链表头，又放回剩余的链表（让它根据剩余链表的头在queue 中进行排序））
                while (!queue.isEmpty()) {
                    p.next = queue.poll();
                    p = p.next;
                    if (p.next != null) queue.add(p.next);
                }
                return dummy.next;
            }
        }    
}