排序算法总结
情绪（稳定性）不稳固：快些选堆
| 排序名称 | 工夫复杂度 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|
| 抉择排序 | O(n^2) | O(1) | 不稳固 | 运行工夫和输出无关；数据挪动是起码的 |
| 插入排序 | O(n^2)，齐全有序变成O(n) | O(1) | 稳固 | 排序工夫取决于初始值（应用替换形式） |
| 冒泡排序 | O(n^2)，齐全有序变成O(n) | O(1) | 稳固 | |
| 归并排序 | O(nlogn)，齐全有序变成O(n) | O(n) | 稳固 | 求解逆序对、小和、染色等问题 |
| 疾速排序 | O(nlogn)，含有雷同元素数组，三路快排O(n) | O(1) | 不稳固 | 求解topK等问题 |
| 堆排序 | O(nlogn) | O(1) | 不稳固 | 实现优先队列 |
| 希尔排序 | O(nlogn)-O(n^2) | O(1) | 不稳固 | 分组思维 |
抉择排序
public class SelectionSort { private SelectionSort() { } // 默写版 public static void selectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[minIndex] < arr[j] ? minIndex : j; } swap(arr, i, minIndex); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 抉择排序1:从前到后选最小 public static <E extends Comparable<E>> void selectionSort(E[] arr) { for (int i = 0; i < arr.length; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // 循环不变量：minIndex永远指向最小的元素 minIndex = arr[minIndex].compareTo(arr[j]) < 0 ? minIndex : j; } swap(arr, i, minIndex); } } // 抉择排序2从后到前选最大 public static <E extends Comparable<E>> void selectionSort1(E[] arr) { for (int i = arr.length - 1; i >= 0; i--) { int maxIndex = i; for (int j = i - 1; j >= 0; j--) { maxIndex = arr[j].compareTo(arr[maxIndex]) > 0 ? j : maxIndex; } swap(arr, i, maxIndex); } } private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}插入排序
public class InsertionSort { private InsertionSort() { } // 默写版 private static void insertSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int temp = arr[i]; int j; // 从后往前插 for (j = i; j - 1 >= 0 && temp < arr[j - 1]; j--) { arr[j] = arr[j - 1]; } arr[j] = temp; } } // 插入排序1:取出元素插入，前面希尔排序会用到这种形式 public static <E extends Comparable<E>> void insertSort1(E[] data) { // 外层循环：遍历每个数组元素，i右边曾经排好序，左边待排序 for (int i = 0; i < data.length; i++) { // 取出以后遍历第一个元素，将它插入到后面曾经排好序的数组中，适合的地位 E temp = data[i]; // 内层循环：遍历右边曾经排好序的数组 int j; // &&左边的条件不能下放！因为j--会对一个位移 for (j = i; j - 1 >= 0 && temp.compareTo(data[j - 1]) < 0; j--) { data[j] = data[j - 1]; } // 内层产生挪动，空出的j地位赋值给temp // 内层没有产生挪动，temp原地赋值给本人 data[j] = temp; } } // 插入排序2:应用替换，性能没有下面好 public static <E extends Comparable<E>> void insertSort2(E[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j].compareTo(arr[j + 1]) > 0; j++) { swap(arr, j, j + 1); } } } private static <E> void swap(E[] arr, int j, int i) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; }}练习题
LC147_对链表进行排序
public class Solution { public ListNode insertionSortList(ListNode head) { if (head == null) { return null; } // 初始化三个指针：dummyNode避免cur插入到head地位 ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode lastSorted = head; ListNode cur = head.next; // cur指针遍历，循环完结条件是cur==null while (cur != null) { // lastSorted后移条件 if (lastSorted.val <= cur.val) { lastSorted = lastSorted.next; } else { // 否则,从头遍历链表找最初<=cur.val的节点 ListNode pre = dummyNode; while (pre.next.val <= cur.val) { pre = pre.next; } // 将cur插入到pre后一位，扭转三者指向 lastSorted.next = cur.next; cur.next = pre.next; pre.next = cur; } // cur为待插入结点=last后一位 cur = lastSorted.next; } // 返回dummyNode下一位 return dummyNode.next; }}冒泡排序
public class BubbleSort { private BubbleSort() { } // 默写版 private static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean isSwap = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap1(arr, j, j + 1); isSwap = true; } } if (!isSwap) { break; } } } // 不应用额定空间，不思考数字越界的替换 private static void swap1(int[] arr, int i, int j) { arr[j] = arr[i] + arr[j]; arr[i] = arr[j] - arr[i]; arr[j] = arr[j] - arr[i]; } // 冒泡排序惯例写法:从后往前比拟，这种写法比拟好记 public static <E extends Comparable<E>> void bubbleSort0(E[] arr) { // 只须要n-1层内部循环 for (int i = arr.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (arr[j].compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); } } } } // 冒泡排序1:优化设置替换标记位 public static <E extends Comparable<E>> void bubbleSort1(E[] arr) { // 外层实现比拟次数：n-1次 for (int i = 0; i < arr.length - 1; i++) { // 优化：设置替换标记位 boolean isSwap = false; // 内层实现相邻元素比拟：每趟只比拟j和j+1的元素 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j].compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); isSwap = true; } } // 内层没有产生替换，阐明后面曾经都排好序了，就不必再次比拟 if (!isSwap) { break; } } } // 冒泡排序2:优化设置最初替换地位，勾销掉i++ public static <E extends Comparable<E>> void bubbleSort2(E[] arr) { for (int i = 0; i < arr.length - 1; ) { int swapNextIndex = 0; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j].compareTo(arr[j + 1]) > 0) { swap(arr, j, j + 1); // 最初替换地位必定是靠后的j+1 swapNextIndex = j + 1; } } i = arr.length - swapNextIndex; } } private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}希尔排序
希尔排序是对插入排序的一种改良尝试，每次基于肯定距离的的两数进行排序，直到距离为1再进行插入排序，此时简直有序插入排序效率变高
public class ShellSort { private ShellSort() { } /** * 希尔排序:对插入排序一种优化，又叫放大增量排序，每次将数组一个元素与雷同增量区间比拟排序，直到增量为1 */ // 希尔排序1:利用插入排序更改 public static <E extends Comparable<E>> void shellSort1(E[] arr) { // 希尔的步长 int step = arr.length / 2; while (step >= 1) { // 插入排序 insertSort(arr, step); step = step / 2; } } private static <E extends Comparable<E>> void insertSort(E[] arr, int step) { for (int i = step; i < arr.length; i++) { E t = arr[i]; int j; for (j = i; j - step >= 0 && t.compareTo(arr[j - step]) < 0; j -= step) { arr[j] = arr[j - step]; } arr[j] = t; } } // 希尔排序2：三重循环 public static <E extends Comparable<E>> void shellSort2(E[] arr) { // 希尔的步长 int step = arr.length / 2; while (step >= 1) { // start是每个子数组的起始地位 for (int start = 0; start < step; start++) { // 以下是应用插入排序 // 对每个子数组进行插入排序:data[start+step,start+2h...data.length-1] for (int i = start + step; i < arr.length; i += step) { E temp = arr[i]; int j; // 前一个元素是j-step for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) { arr[j] = arr[j - step]; } arr[j] = temp; } } step = step / 2; } } // 希尔排序3：批改步长序列 public static <E extends Comparable<E>> void shellSort3(E[] arr) { // 希尔的步长 int step = 1; while (step < arr.length) { step = step * 3 + 1; } while (step >= 1) { // 对每个子数组进行插入排序:data[start+h,start+2h...data.length-1] for (int i = step; i < arr.length; i++) { E temp = arr[i]; int j; // 前一个元素是j-step for (j = i; j - step >= 0 && temp.compareTo(arr[j - step]) < 0; j -= step) { arr[j] = arr[j - step]; } arr[j] = temp; } step = step / 3; } }}练习题
LC506_绝对名次
public class Solution { // 排序法 public String[] findRelativeRanks1(int[] score) { String[] result = new String[score.length]; // 复制原数组到排序数组 int[] sorted = new int[score.length]; System.arraycopy(score, 0, sorted, 0, score.length); Arrays.sort(sorted); for (int i = 0; i < score.length; i++) { int index = score.length - Arrays.binarySearch(sorted, score[i]); switch (index) { case 1: result[i] = "Gold Medal"; break; case 2: result[i] = "Silver Medal"; break; case 3: result[i] = "Bronze Medal"; break; default: result[i] = String.valueOf(index); } } return result; } // 计数排序法 public String[] findRelativeRanks2(int[] score) { String[] result = new String[score.length]; int max = Integer.MIN_VALUE; for (int num : score) { max = Math.max(max, num); } int[] array = new int[max + 1]; // 初始化arr数组,下标为score的值，arr[i]为该元素的排名 for (int i = 0; i < score.length; i++) { array[score[i]] = i + 1; } int rank = 1; for (int i = array.length - 1; i >= 0; i--) { if (array[i] != 0) { switch (rank) { case 1: result[array[i] - 1] = "Gold Medal"; break; case 2: result[array[i] - 1] = "Silver Medal"; break; case 3: result[array[i] - 1] = "Bronze Medal"; break; default: result[array[i] - 1] = String.valueOf(rank); } rank++; } } return result; }}归并排序
第一种版本是进行优化后的，便于对了解数组中的逆序对问题！
public class MergeSort { private MergeSort() { } public static <E extends Comparable<E>> void mergerSort(E[] arr) { // 优化:只生成一次辅助数组，使得merge中没有偏移量的操作了 // Arrays.copyOf(指标数组,开区间) E[] temp = Arrays.copyOf(arr, arr.length); mergerSort(arr, 0, arr.length - 1, temp); } private static <E extends Comparable<E>> void mergerSort(E[] arr, int l, int r, E[] temp) { // 优化2：指定长度内，可应用间接插入排序优化，但这种优化成果不显著，所以这里放弃应用 if (l >= r) { return; } // 先递归合成 int mid = l + (r - l) / 2; mergerSort(arr, l, mid, temp); mergerSort(arr, mid + 1, r, temp); // 优化1：[l,mid]曾经排序好，[mid+1...]后的地位 if (arr[mid].compareTo(arr[mid + 1]) > 0) { merge(arr, l, mid, r, temp); } } private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) { // System.arraycopy(复制数组,复制数组起始地位,指标数组,指标数组起始地位,复制数组长度开区间) System.arraycopy(arr, l, temp, l, r - l + 1); // p遍历temp[l,mid];q遍历temp[mid+1,r] int p = l, q = mid + 1; // i遍历arr[l,r] for (int i = l; i <= r; i++) { if (p > mid) { arr[i] = temp[q++]; } else if (q > r) { arr[i] = temp[p++]; } else if (temp[p].compareTo(temp[q]) <= 0) { arr[i] = temp[p++]; } else { arr[i] = temp[q++]; } } }}第二版是左程元上课时教的，集体认为是最容易了解和背诵的版本，但不利于书写数组逆序对问题
public class MergeSort1 { private MergeSort1() { } // 左神归并排序写法 public static void mergeSort(int[] arr) { if (arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(int[] arr, int l, int r) { if (l == r) { return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void merge(int[] arr, int l, int m, int r) { int[] temp = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while (p1 <= m && p2 <= r) { temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { temp[i++] = arr[p1++]; } while (p2 <= r) { temp[i++] = arr[p2++]; } for (i = 0; i < temp.length; i++) { arr[l + i] = temp[i]; } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}练习题
LC88_合并两个有序数组
十分高频的一道题
public class Solution { /** * 合并两个有序数组，num1长度大于m+n,m是num1长度，n是nums2长度 */ // 办法一:逆向双指针，不应用额定数组 public void merge(int[] nums1, int m, int[] nums2, int n) { // 初始化为各自-1的地位 int p1 = m - 1, p2 = n - 1, tail = m + n - 1; // temp存较大的数，从后往前放 int temp; while (p1 >= 0 || p2 >= 0) { // temp获取较大值 if (p1 == -1) { temp = nums2[p2--]; } else if (p2 == -1) { temp = nums1[p1--]; } else if (nums1[p1] < nums2[p2]) { temp = nums2[p2--]; } else { temp = nums1[p1--]; } // 利用尾指针寄存temp nums1[tail--] = temp; } } // 办法二:正向双指针，须要应用额定数组 public void merge1(int[] nums1, int m, int[] nums2, int n) { // 初始化从0开始 int p1 = 0, p2 = 0; // 辅助变量存比拟后的值 int temp; int[] help = new int[m + n]; while (p1 < m || p2 < n) { if (p1 == m) { temp = nums2[p2++]; } else if (p2 == n) { temp = nums1[p1++]; } else if (nums1[p1] < nums2[p2]) { temp = nums1[p1++]; } else { temp = nums2[p2++]; } // 辅助数组放下temp help[p1 + p2 - 1] = temp; } // 从help数组的0地位开始复制m+n个元素到nums1数组中，nums1数组从0地位开始承受 System.arraycopy(help, 0, nums1, 0, m + n); }}剑指25_合并两个有序链表
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // dummyNode便于返回头结点 ListNode dummyNode = new ListNode(0); // cur初始化指向dummyNode ListNode cur = dummyNode; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } // 每次循环，cur后移 cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummyNode.next; }}剑指52_数组中的逆序对问题
这道题十分高频，并且对于了解归并排序的归并操作有很大帮忙，倡议dubug多看几次
public class Solution { private int res; // 归并排序法，如果右边大，那么右边未归并的局部就是造成逆序对的个数 public int reversePairs(int[] nums) { int[] temp = new int[nums.length]; res = 0; sort(nums, 0, nums.length - 1, temp); return res; } private void sort(int[] arr, int l, int r, int[] temp) { if (l >= r) { return; } int mid = l + (r - l) / 2; sort(arr, l, mid, temp); sort(arr, mid + 1, r, temp); // >保障了，如果j地位小于i地位的，右边未排序中的必定是逆序对 if (arr[mid] > arr[mid + 1]) { merge(arr, l, mid, r, temp); } } private void merge(int[] arr, int l, int mid, int r, int[] temp) { System.arraycopy(arr, l, temp, l, r - l + 1); int i = l, j = mid + 1; // 每轮循环为 arr[k] 赋值 for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = temp[j++]; } else if (j > r) { arr[k] = temp[i++]; } else if (temp[i] <= temp[j]) { arr[k] = temp[i++]; } else { // 判断逆序对条件：temp[i]>temp[j] res += mid - i + 1; arr[k] = temp[j++]; } } }}疾速排序
单路快排
public class QuickSort { private QuickSort() { } // 单路快排默写版 public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } Random random = new Random(); quickSort(arr, 0, arr.length - 1, random); } private static void quickSort(int[] arr, int l, int r, Random random) { if (l >= r) { return; } int p = partition(arr, l, r, random); quickSort(arr, l, p - 1, random); quickSort(arr, p + 1, r, random); } private static int partition(int[] arr, int l, int r, Random random) { swap(arr, l, l + random.nextInt(r - l + 1)); int less = l; for (int i = l + 1; i <= r; i++) { if (arr[i] < arr[l]) { swap(arr, i, ++less); } } swap(arr, l, less); return less; } public static <E extends Comparable<E>> void quickSort1(E[] arr) { Random random = new Random(); quickSort1(arr, 0, arr.length - 1, random); } private static <E extends Comparable<E>> void quickSort1(E[] arr, int l, int r, Random random) { // 不仅仅是递归完结条件,更是上轮l和r保障左小右大的条件 if (l >= r) return; // 将数组分区，随机取得一个基数，小于基数放右边，大于基数放左边，返回基数最终地位下标 int p = partition1(arr, l, r, random); // 对上一轮基数最终地位的右边，递归排序 quickSort1(arr, l, p - 1, random); // 对上一轮基数最终地位的左边，递归排序 quickSort1(arr, p + 1, r, random); } // partition:数组分区，随机取得一个基数，小于基数放右边，大于基数放左边，返回基数最终地位下标 private static <E extends Comparable<E>> int partition1(E[] arr, int l, int r, Random random) { // 随机替换l和p地位上的数，解决数组有序问题 int p = l + random.nextInt(r - l + 1); swap1(arr, l, p); // j初始化l int j = l; // 遍历l后续数组元素，j指向<arr[l]的最初一个数， for (int i = l + 1; i <= r; i++) { if (arr[i].compareTo(arr[l]) < 0) { j++; swap1(arr, i, j); } } // 循环跳出,替换基数与小于基数最初一个数 swap1(arr, l, j); // 因为上一步替换，此时arr[j]就是基数最终地位，返回j return j; } private static <E> void swap1(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; } private static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }}双路快排
public class QuickSort2Ways { private QuickSort2Ways() { } // 双路疾速排序 public static <E extends Comparable<E>> void quickSort2ways(E[] arr) { Random random = new Random(); quickSort2ways(arr, 0, arr.length - 1, random); } private static <E extends Comparable<E>> void quickSort2ways(E[] arr, int l, int r, Random random) { if (l >= r) return; int p = partition(arr, l, r, random); quickSort2ways(arr, l, p - 1, random); quickSort2ways(arr, p + 1, r, random); } private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) { int p = l + random.nextInt(r - l + 1); swap(arr, l, p); // i指向<=的区间的下一个元素，j指向>=区间的前一个元素 int i = l + 1, j = r; while (true) { while (i <= j && arr[i].compareTo(arr[l]) < 0) { i++; } while (i <= j && arr[j].compareTo(arr[l]) > 0) { j--; } // 循环条件:i<j;相同就是完结条件 if (i >= j) { break; } // 循环未完结,此时arr[i]>=基数,arr[j]<=基数，替换使得前小后大 swap(arr, i, j); // 挪动指针 i++; j--; } // 循环跳出条件i>=j,arr[j]指向<=arr[l]的最初一个数,替换(l,j) swap(arr, l, j); return j; } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; }}三路快排
public class QuickSort3Ways { private QuickSort3Ways() { } // 三路快排 public static <E extends Comparable<E>> void quickSort3ways(E[] arr) { Random random = new Random(); quickSort3ways(arr, 0, arr.length - 1, random); } private static <E extends Comparable<E>> void quickSort3ways(E[] arr, int l, int r, Random random) { if (l >= r) return; int p = l + random.nextInt(r - l + 1); swap(arr, l, p); // 外围：arr[l+1,lt]<v ; arr[lt+1,i-1]=v ; arr[gt,r]>v // less指向<的最初一个元素，i指针遍历，more指向>的第一个元素 int less = l, i = l + 1, more = r + 1; while (i < more) { if (arr[i].compareTo(arr[l]) < 0) { less++; swap(arr, i, less); i++; } else if (arr[i].compareTo(arr[l]) > 0) { more--; swap(arr, i, more); // 原先的gt--后的值没有比拟过，i持续指向它，不必i++ } else { // arr[i]==arr[l] i++; } } swap(arr, l, less); // 三路快排摈弃掉两头的局部，不再递归 quickSort3ways(arr, l, less - 1, random); quickSort3ways(arr, more, r, random); } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; }}练习题
LC69_少数元素
public class Solution { // 排序法 public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; } // map法 public int majorityElement1(int[] nums) { Map<Integer, Integer> map = countMap(nums); for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() > (nums.length) / 2) { return entry.getKey(); } } throw new RuntimeException("not have num"); } private Map<Integer, Integer> countMap(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) + 1); } } return map; } // 候选人投票法 public int majorityElement2(int[] nums) { int res = nums[0], res_count = 1; for (int i = 1; i < nums.length; i++) { if (res == nums[i]) { res_count++; } else { res_count--; if (res_count == 0) { // 候选人投票数为0,重置候选人为下一个数 res = nums[i]; res_count = 1; } } } return res; }}堆排序
public class HeapSort { private HeapSort() { } // 基础知识:设根节点0开始为i，左孩子2i+1,右孩子2i+2 // 设左右孩子为i，父亲节点为(i-1)/2 // 堆排序：原地堆排序 public static <E extends Comparable<E>> void heapSort(E[] arr) { if (arr.length <= 1) { return; } // 1.对数组最右子树父节点顺次上浮操作，循环完结arr[0]=数组max for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) { siftUp(arr, i, arr.length); } // 2.第一次arr[0]=max,与数组开端替换，每次替换，都对[0,i)进行下沉操作使得arr[0]=max for (int i = arr.length - 1; i >= 0; i--) { swap(arr, 0, i); siftUp(arr, 0, i); } } // 对 arr[0,bound)所造成的最大堆中,索引为parentIndex的父亲和其左右孩子，进行最大值上浮操作 private static <E extends Comparable<E>> void siftUp(E[] arr, int parentIndex, int bound) { while (2 * parentIndex + 1 < bound) { int left = 2 * parentIndex + 1; if (left + 1 < bound && arr[left + 1].compareTo(arr[left]) > 0) { // left指向最大孩子节点下标 left++; } // 循环完结条件:父元素比孩子最大还大 if (arr[parentIndex].compareTo(arr[left]) >= 0) { break; } // 否则:替换父元数和孩子最大值 swap(arr, parentIndex, left); // 父指针指向孩子最大值下标 parentIndex = left; } } private static <E> void swap(E[] arr, int i, int j) { E t = arr[i]; arr[i] = arr[j]; arr[j] = t; }}练习题
LC23_合并K个升序数组
public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } // 最小值堆:依照lists中node的值从小到大排列。雷同的值依照原先顺序排列 PriorityQueue<ListNode> minQueue = new PriorityQueue<>(lists.length, (node1, node2) -> { if (node1.val < node2.val) { return -1; } else if (node1.val == node2.val) { return 0; } else { return 1; } }); // 哑结点和遍历指针 ListNode dummyNode = new ListNode(0); ListNode cur = dummyNode; // 遍历原lists，将所有结点放入最小值堆中 for (ListNode node : lists) { if (node != null) { minQueue.add(node); } } // 遍历最小值堆，每次让cur指向出队的元素，cur后移，再让cur.next从新入队，始终让堆顶放弃最小值 while (!minQueue.isEmpty()) { cur.next = minQueue.poll(); cur = cur.next; if (cur.next != null) { minQueue.add(cur.next); } } return dummyNode.next; }}