题解 | 牛群的合并

1. 2路归并

import java.util.*;

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode guard = new ListNode(0);
        ListNode t = guard;
        while (l1 != null && l2 != null) {
            if (l2.val < l1.val) {
                t.next = l2;
                l2 = l2.next;
            } else {
                t.next = l1;
                l1 = l1.next;
            }
            t = t.next;
        }
        if (l1 != null) {
            t.next = l1;
        } else {
            t.next = l2;
        }
        return guard.next;
    }

    public ListNode mergeKListsHelper(ListNode[] lists, final int l, final int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }

        final int m = l + ((r - l) >> 1);
        return mergeTwoLists(mergeKListsHelper(lists, l, m), mergeKListsHelper(lists, m + 1, r));

    }

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

1. PriorityQueue 的用法。

import java.util.*;

public class Solution {
    public ListNode mergeKLists (ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        Comparator<ListNode> nodeComparator = (o1, o2) -> o1.val - o2.val;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, nodeComparator);
        for (ListNode list: lists) {
            if (list != null) {
                minHeap.add(list);
            }
        }

        ListNode guard = new ListNode(0);
        ListNode t = guard;
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            if (node.next != null) {
                minHeap.add(node.next);
            }
            t.next = node;
            t = t.next;
        }
        return guard.next;
    }