23. Merge k Sorted Lists

recusion

public ListNode mergeKLists(ListNode[] lists) {
    return partition(lists, 0, lists.length - 1);
}

public ListNode partition(ListNode[] lists, int l, int r) {
    if (l == r) return lists[l];
    else if (l < r) {
        int m = (l + r) >>> 1;
        ListNode l1 = partition(lists, l, m);
        ListNode l2 = partition(lists, m + 1, r);
        return merge(l1, l2);
    }
    return null;
}

public ListNode merge(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) return (l1 != null) ? l1 : l2;
    if (l1.val < l2.val) {
        l1.next = merge(l1.next, l2);
        return l1;
    } else {
        l2.next = merge(l1, l2.next);
        return l2;
    }
}

heap

优先队列重写ListNode的Comparator从小到大取点。

public ListNode mergeKLists2(ListNode[] lists) {
    if (lists.length == 0) return null;
    PriorityQueue<ListNode> q = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
        public int compare(ListNode l1, ListNode l2) {
            if (l1.val < l2.val) {
                return -1;
            } else if (l1.val == l2.val) {
                return 0;
            } else {
                return 1;
            }
        }
    });

    ListNode dummy = new ListNode(0), head = dummy;
    for (ListNode list : lists) {
        if (list != null) {
            q.add(list);
        }
    }

    while (!q.isEmpty()) {
        head.next = q.poll();
        head = head.next;

        if (head.next != null) {
            q.add(head.next);
        }
    }
    return dummy.next;
}

naive

一开始的实现，拼一拼

public ListNode mergeKLists(ListNode[] lists) {
    List<ListNode> newList = new ArrayList<>(Arrays.asList(lists));
    while (newList.size() >= 2) {
        ListNode list = merge2List(newList.get(newList.size() - 1), newList.get(newList.size() - 2));
        newList.add(0, list);
        newList.remove(newList.size() - 1);
        newList.remove(newList.size() - 1);
    }
    if (newList.size() == 1) return newList.get(0);
    return null;
}