@@ -0,0 +1,2926 @@
+package main.algorithm.leetcode;%0A%0Aimport main.algorithm.leetcode.structure.ListNode;%0Aimport main.algorithm.leetcode.util.LCUtil;%0Aimport org.junit.Test;%0A%0A/**%0A * Title : main.algorithm.leetcode %3Cbr%3E%0A * Description :%0A *   Runtime: 2 ms, faster than 94.10%25 of Java online submissions for Merge k Sorted Lists.%0A *   Memory Usage: 45.3 MB, less than 6.53%25 of Java online submissions for Merge k Sorted Lists.%0A * @author chile%0A * @version 1.0%0A * @date 2020/3/11 18:10%0A */%0Apublic class MergeKSortedLists %7B%0A%0A    class Solution %7B%0A        public ListNode mergeKLists(ListNode%5B%5D lists) %7B%0A            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;%0A            for (ListNode head : lists) %7B%0A                if (head == null) %7B%0A                    continue;%0A                %7D%0A                min = Math.min(min, head.val);%0A                while (head.next != null) %7B%0A                    head = head.next;%0A                %7D%0A                max = Math.max(max, head.val);%0A            %7D%0A%0A            int numRange = max - min;%0A            if (numRange %3C 0) %7B%0A                return null;%0A            %7D%0A%0A            int%5B%5D solts = new int%5BnumRange + 1%5D;%0A%0A            for (ListNode head : lists) %7B%0A                if (head == null) %7B%0A                    continue;%0A                %7D%0A                do %7B%0A                    solts%5Bhead.val - min%5D++;%0A                    head = head.next;%0A                %7D while (head != null);%0A            %7D%0A%0A            ListNode resultHead = null, tempNode = null;%0A            for (int i = 0; i %3C solts.length; i++) %7B%0A                if (solts%5Bi%5D == 0) %7B%0A                    continue;%0A                %7D%0A                for (int j = 0; j %3C solts%5Bi%5D; j++) %7B%0A                    ListNode node = new ListNode(i + min);%0A                    if (resultHead == null) %7B%0A                        resultHead = node;%0A                        tempNode = resultHead;%0A                    %7D else %7B%0A                        tempNode.next = node;%0A                        tempNode = node;%0A                    %7D%0A                %7D%0A            %7D%0A%0A            return resultHead;%0A        %7D%0A    %7D%0A%0A    @Test%0A    public void test1() %7B%0A        ListNode list1 = LCUtil.createListWith(3);%0A        ListNode list2 = LCUtil.createListWith(9);%0A        ListNode list3 = LCUtil.createListWith(6);%0A        ListNode%5B%5D lists = new ListNode%5B3%5D;%0A        lists%5B0%5D = list1;%0A        lists%5B1%5D = list2;%0A        lists%5B2%5D = list3;%0A        ListNode node = new Solution().mergeKLists(lists);%0A        do %7B%0A            System.out.println(node.val);%0A            node = node.next;%0A        %7D while (node != null);%0A%0A    %7D%0A%0A    @Test%0A    public void test2() %7B%0A        ListNode list1 = LCUtil.createListWith(1);%0A        ListNode%5B%5D lists = new ListNode%5B3%5D;%0A        lists%5B0%5D = list1;%0A        ListNode node = new Solution().mergeKLists(lists);%0A        do %7B%0A            System.out.println(node.val);%0A            node = node.next;%0A        %7D while (node != null);%0A%0A    %7D%0A%0A%7D%0A

Merge k Sorted Lists 基数排序解法