排序｜ Leetcode 148
2023-03-03 本文已影响0人
三更冷
1、题目
给你链表的头结点 head ，请将其按升序排列并返回排序后的链表 。
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
2、思路
符合 O(n log n) 时间复杂度要求有快速排序，归并排序，堆排序等。快速排序和堆排序虽然时间复杂度也为 O(n logn)，但是它们需要使用数组来实现，空间复杂度也不符合要求。
如果要使用快速排序对链表进行排序，则需要对链表进行原地分区操作（in-place partition）。由于链表不支持随机访问，因此无法像数组那样在 O(1) 时间内定位元素。在链表中进行原地分区操作的时间复杂度最坏情况下为 O(n^2)，因此快速排序不是链表排序的首选算法。
堆排序需要使用 O(n) 的额外空间来存储堆，因此无法实现常数空间复杂度。另外，由于堆排序对数组的随机访问有较高的要求，无法直接应用于链表中，较难使用堆排序解决这个问题。
归并排序利用递归来交换数字，天然适合链表这种结构。
① 自顶向下的归并排序（递归法）
首先我们知道归并排序的思想，即将待排序的序列递归地分成两个子序列，分别进行排序，最后再将两个有序子序列合并成一个有序序列。
对于链表来说，找到链表的中间节点可以使用快慢指针的方法，然后将链表断开成两个子链表，分别递归进行排序，最后合并两个有序子链表。
时间复杂度：O(nlogn)，空间复杂度：O(logn)，其中n是链表的长度。空间复杂度主要取决于递归调用的栈空间。
② 自底向上的归并排序（迭代法）
时间复杂度：O(nlog n)，空间复杂度：O(1)。它的空间复杂度比自顶向下的归并排序要优秀，因为它不需要递归调用，避免了递归栈的空间开销。
3、递归版
public class Solution {
public ListNode sortList(ListNode head) {
// 1、递归结束条件
if (head == null || head.next == null) {
return head;
}
// 2、找到链表中间节点并断开链表 & 递归下探
ListNode midNode = middleNode(head);
ListNode rightHead = midNode.next;
midNode.next = null;
// 分治，递归排序左右两个链表
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 3、当前层业务操作（合并有序链表）
return mergeTwoLists(left, right);
}
// 找到链表中间节点（876. 链表的中间结点）
// 奇数个节点找到中点，偶数个节点找到中心左边的节点。
private ListNode middleNode(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 合并两个有序链表（21. 合并两个有序链表）
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode sentry = new ListNode(-1);
ListNode curr = sentry;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return sentry.next;
}
}
4、迭代法
具体实现步骤如下：
- 定义一个变量 step，表示每次归并时子数组的长度，初始值为 1。
- 对于每个 step，从链表头开始扫描链表，将链表分成若干个长度为 step 的子链表，并对每个子链表进行归并排序。
- 将归并排序后的子链表依次两两合并，得到长度为 2*step 的子链表。
- 重复步骤 3，直到 step >= 链表长度，排序完成。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
int len = getLength(head);
ListNode dummy = new ListNode(0, head);
for (int step = 1; step < len; step <<= 1) {
ListNode prev = dummy, cur = dummy.next;
while (cur != null) {
ListNode left = cur, right = cut(cur, step);
cur = cut(right, step);
prev.next = mergeTwoLists(left, right);
while (prev.next != null) {
prev = prev.next;
}
}
}
return dummy.next;
}
// 获取链表长度
private int getLength(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
// 将链表分为前 n 个节点和后面的节点，并返回后面节点的头结点
private ListNode cut(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode p = head;
while (--n > 0 && p != null) {
p = p.next;
}
if (p == null) {
return null;
}
ListNode next = p.next;
p.next = null;
return next;
}
// 合并两个有序链表
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode sentry = new ListNode(-1);
ListNode curr = sentry;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return sentry.next;
}
}
5、快排版
如果想要使用快速排序解决这个问题，可以考虑先将链表转换为数组，然后对数组进行原地分区操作，最后再将排序后的数组转换为链表。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 将链表转换为数组
List<Integer> arr = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
arr.add(cur.val);
cur = cur.next;
}
// 对数组进行原地分区操作
quickSort(arr, 0, arr.size() - 1);
// 将排序后的数组转换为链表
ListNode dummy = new ListNode(0);
cur = dummy;
for (int i = 0; i < arr.size(); i++) {
cur.next = new ListNode(arr.get(i));
cur = cur.next;
}
return dummy.next;
}
private void quickSort(List<Integer> arr, int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
private int partition(List<Integer> arr, int left, int right) {
int pivotIndex = left;
int pivot = arr.get(pivotIndex);
swap(arr, pivotIndex, right);
int i = left;
for (int j = left; j < right; j++) {
if (arr.get(j) < pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private void swap(List<Integer> arr, int i, int j) {
int tmp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, tmp);
}
}
6、堆排序版
class Solution {
public ListNode sortList(ListNode head) {
// 将链表转换为堆
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
while(head != null){
minHeap.offer(head);
head=head.next;
}
// 进行堆排序
ListNode guard = new ListNode(0), curr = guard;
while(!minHeap.isEmpty()){
curr.next = minHeap.poll();
curr = curr.next;
curr.next = null;
}
return guard.next;
}
}
6、测试用例（自测）
@Data
public class ListNode {
public int val;
public ListNode next;
public ListNode() {}
public ListNode(int val) { this.val = val; }
public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class SolutionTest {
@Test
public void testSortList() {
Solution solution = new Solution();
// 测试用例 1: 给定一个无序链表 [4,2,1,3]，排序后的链表为 [1,2,3,4]
ListNode head1 = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
ListNode expected1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
ListNode actual1 = solution.sortList(head1);
assertEquals(expected1, actual1);
// 测试用例 2: 给定一个已排序的链表 [1,2,3,4]，排序后的链表仍为 [1,2,3,4]
ListNode head2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
ListNode expected2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
ListNode actual2 = solution.sortList(head2);
assertEquals(expected2, actual2);
// 测试用例 3: 给定一个只有一个节点的链表 [1]，排序后的链表仍为 [1]
ListNode head3 = new ListNode(1);
ListNode expected3 = new ListNode(1);
ListNode actual3 = solution.sortList(head3);
assertEquals(expected3, actual3);
// 测试用例 4: 给定一个空链表，排序后的链表仍为空
ListNode head4 = null;
ListNode expected4 = null;
ListNode actual4 = solution.sortList(head4);
assertEquals(expected4, actual4);
}
}
6、估计执行用时和内存消耗（自测）
用于估计 Solution 类中的 sortList 方法。可以多次运行这段代码，观察平均执行时间和内存消耗。注意，由于 JVM 的运行机制，执行时间和内存消耗可能因为多次执行而产生波动。
import java.util.Random;
public class PerformanceTest {
public static void main(String[] args) {
// 生成一个长度为 1000 的随机链表
ListNode head = generateRandomList(1000);
// 创建一个 Solution 实例
Solution4 solution = new Solution4();
// 计时开始
long startTime = System.nanoTime();
// 调用 sortList 方法进行排序
ListNode sortedList = solution.sortList(head);
// 计时结束
long endTime = System.nanoTime();
// 输出排序结果及执行时间和内存消耗
System.out.println("Sorted list: " + sortedList);
System.out.printf("Execution time: %d μs\n", (endTime - startTime) / 1000);
System.out.printf("Memory usage: %.2f MB\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1024.0 / 1024.0);
}
private static ListNode generateRandomList(int length) {
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
Random random = new Random();
for (int i = 0; i < length; i++) {
curr.next = new ListNode(random.nextInt(100000));
curr = curr.next;
}
return dummy.next;
}
}
可以发现，执行时间和内存消耗：递归版≈迭代法<快排版<堆排序版
参考文章：
https://zhuanlan.zhihu.com/p/85122573
https://zhuanlan.zhihu.com/p/441456647
https://www.cnblogs.com/skywang12345/p/3602369.html
