2023-11-09T19:02:00Z
你已经掌握了排序算法的奥秘了，那么就来一场试炼罢。
LeetCode 148. Sort List
1 Selection sort
创建一个 sentinel node，每次选出最大的 node，append 到 sentinel 后面。
class Solution {
public ListNode sortList(ListNode head) {
return selectionSort(head);
}
private static ListNode selectionSort(ListNode head) {
ListNode sentinel = new ListNode(0, null);
while (head != null) {
ListNode largestPrev = findLargestPrev(head);
ListNode largest = largestPrev.next;
if (largest == head) {
head = head.next;
}
largestPrev.next = largest.next;
largest.next = sentinel.next;
sentinel.next = largest;
}
return sentinel.next;
}
/** return the previous node of the largest node */
private static ListNode findLargestPrev(ListNode head) {
ListNode largestPrev = new ListNode(0, head);
ListNode currentPrev = largestPrev;
while (currentPrev.next != null) {
if (currentPrev.next.val > largestPrev.next.val) {
largestPrev = currentPrev;
}
currentPrev = currentPrev.next;
}
return largestPrev;
}
}
时间复杂度 O(N^{2}) ，空间复杂度 O(1) ，不出意外的 TLE。
2 Insertion sort
数组的 insertion sort 是从头开始遍历，如果比左边小就向左交换位置。对于 SLList，依然是创建一个 sentinel node，从 head 节点开始一个一个插入 sentinel 之后，若比后面节点大则向右交换。
class Solution {
public ListNode sortList(ListNode head) {
return insertionSort(head);
}
private static ListNode insertionSort(ListNode head) {
ListNode sentinel = new ListNode(0, null);
while (head != null) {
ListNode temp = head;
head = head.next;
temp.next = sentinel.next;
sentinel.next = temp;
swapHelper(sentinel);
}
return sentinel.next;
}
/** swap first node of sorted list rightwards while larger than right */
private static void swapHelper(ListNode sentinel) {
ListNode prev = sentinel;
ListNode newly = sentinel.next;
while (newly.next != null && newly.val > newly.next.val) {
prev.next = newly.next;
newly.next = newly.next.next;
prev.next.next = newly;
prev = prev.next;
}
}
}
时间复杂度 O(N^{2}) ，空间复杂度 O(1) ，又是令人欣慰的 TLE。但是这个指针操作比上一个要优雅多了。
3 Mergesort
Divide and conquer. Use top-down mergesort.
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) return null;
return mergesort(head);
}
/** recursively split and merge */
private static ListNode mergesort(ListNode head) {
if (head.next == null) return head;
ListNode mid = split(head);
ListNode leftSorted = mergesort(head);
ListNode rightSorted = mergesort(mid);
return merge(leftSorted, rightSorted);
}
/** split the given list into two and return the pointer to the second half */
private static ListNode split(ListNode head) {
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
return mid;
}
/** merge left list and right list */
private static ListNode merge(ListNode left, ListNode right) {
ListNode sentinel = new ListNode(0, null);
ListNode rear = sentinel;
while (left != null && right != null) {
if (left.val <= right.val) {
ListNode temp = left;
left = left.next;
temp.next = null;
rear.next = temp;
} else {
ListNode temp = right;
right = right.next;
temp.next = null;
rear.next = temp;
}
rear = rear.next;
}
if (left == null) {
while (right != null) {
ListNode temp = right;
right = right.next;
temp.next = null;
rear.next = temp;
rear = rear.next;
}
} else { // right == null
while (left != null) {
ListNode temp = left;
left = left.next;
temp.next = null;
rear.next = temp;
rear = rear.next;
}
}
return sentinel.next;
}
}
时间复杂度 O(NlogN) ，空间复杂度 O(1) ，顺利 AC。
对 SLList 进行 quicksort 用 Java 太难实现了，遂放弃。（因为 Java 方法只能返回一个值，并且不能像 C/C++ 一样传递指针的指针来实现多返回值。）
SLList 的节点只有一个指针空间，故也不能实现 Heapsort。所以 mergesort 事坠吼的。
但是有一点小问题：为了避免 mergesort 的 worst case，在数组版本中首先对待排序数组进行 shuffle，链表好像不是很好进行 shuffle。第二个就是为了方便在 SLList 中进行节点插入删除，我使用了 currentPrev.next == current。但感觉这样很不优雅，不知道有没有什么修改方法。
Insertion sort 中我函数抽象的层次不对，应该把可复用的 swap() 抽象出来，而不是依赖于调用函数的 swapHelper()。