/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    //copy into one and sort
    /*
    public ListNode mergeKLists(List<ListNode> lists) {  
        // write your code here
        if (lists == null || lists.size() == 0) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode head = new ListNode(0);
        int index = 0;
        for (index = 0; index < lists.size(); index++) {
            if (lists.get(index) != null) {
                dummy.next = lists.get(index);
                head = lists.get(index);
                break;
            }
        }
        if (dummy.next == null) {
            return null;
        }

        for (int i = index + 1; i < lists.size(); i++) {
            while (head.next != null) {
                head = head.next;
            }
            if (lists.get(i) == null) {
                continue;
            }
            head.next = lists.get(i);
            head = head.next;
        }


        return sort(dummy.next);
    }

    public ListNode sort(ListNode list) {
        if (list == null) {
            return null;
        }
        if (list.next == null) {
            return list;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = list;
        ListNode slow = dummy;
        ListNode fast = list;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode right = sort(slow.next);
        slow.next = null;
        ListNode left = sort(list);

        return merge(left, right);
    }

    public ListNode merge(ListNode left, ListNode right) {

        ListNode result = new ListNode(0);
        ListNode head = result;
        while (left != null && right != null) {
            if (left.val < right.val) {
                result.next = left;
                left = left.next;
            } else {
                result.next = right;
                right = right.next;
            }
            result = result.next;
        }
        while (left != null) {
            result.next = left;
            left = left.next;
            result = result.next;
        }
        while (right != null) {
            result.next = right;
            right = right.next;
            result = result.next;
        }
        return head.next;

    }

    */

    //heap solution (using priority queue)
    /*
    private Comparator<ListNode> comparator = new Comparator<ListNode>() {
        public int compare(ListNode a, ListNode b) {
            if (a == null) {
                return 1;
            }
            else if (b == null) {
                return -1;
            }
            return a.val - b.val;
        }  
    };

    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        Queue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), comparator);
        //ListNode dummy = new ListNode(0);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                 pq.offer(lists.get(i));
            }
        }
        if (pq.peek() == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (pq.peek() != null) {
            head.next = pq.poll();
            head = head.next;
            if (head.next != null) {
                pq.offer(head.next);
            }
        }
        return dummy.next;

    }

    */

    //method 3:  2 by 2 merge until only two left
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        while (lists.size() > 1) {
            List<ListNode> new_list = new ArrayList<>();
            for (int i = 0; i < lists.size(); i+=2) {
                if (i + 1 < lists.size()) {
                    new_list.add(merge(lists.get(i), lists.get(i + 1)));
                } else {
                    new_list.add(lists.get(i));
                }
            }

            lists = new_list;
        }
        return lists.get(0);
    }

    public ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                head.next = a;
                a = a.next;
            } else {
                head.next = b;
                b = b.next;
            }
            head = head.next;
        }
        while (a != null) {
            head.next = a;
            a = a.next;
            head = head.next;
        }
        while (b != null) {
            head.next = b;
            b = b.next;
            head = head.next;
        }
        return dummy.next;
    }





}