描述
在 O(nlogn) 时间复杂度和常数级的空间复杂度下给链表排序
样例
给出 1->3->2->null，给它排序变成 1->2->3->null.
挑战
分别用归并排序和快速排序做一遍。
PS
常数级复杂度即 O(1) 的复杂度只用一个额外变量
知识点
- quick sort:
平均时间复杂度 O(nlogn)，如果每次选取的切割点都是链表端点，通过 O(1) 的操作使 O(n) 的问题变为 O(n - 1)，最坏情况时间复杂度是 O(n^2)，空间复杂度 O(1)- Merge sort
时间复杂度一直是 O(nlogn)，空间复杂度 O(n)- heap sort
时间复杂度 O(n)，空间复杂度 O(1)
区别
无论是快排还是归并排序都需要用递归，但快排是先整体有序后局部有序，而归并排序是先局部有序再整体有序
代码
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
- Merge Sort
public class Solution {
private ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
// 合并两个链表
private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tail.next = head1;
head1 = head1.next;
} else {
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
}
if (head1 != null) {
tail.next = head1;
} else {
tail.next = head2;
}
return dummy.next;
}
/* 用二分的方式不断地递归细化链表，直到链表变成只有两个结点，
* 然后用 merge 排个序，再一层层返回递归，
* 值得说明的是每退出一层递归都有两个排好序的链表，
* 每一层递归都要 merge 名为 left 和 right 的两个链表
*/
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMiddle(head);
ListNode right = sortList(mid.next);
// 保证 left 是 head 到 mid 的链表,不然 left 还是从 head 开始的整个链表
mid.next = null;
ListNode left = sortList(head);
return merge(left, right);
}
}
- Quick Sort 1
链表快排并不是采用两根指针，一根指针从头到尾
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMedian(head); // O(n)
// 定义每一部分的头指针
ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
ListNode rightDummy = new ListNode(0), rightTail = rightDummy;
ListNode middleDummy = new ListNode(0), middleTail = middleDummy;
// 快排交换结点的模板
while (head != null) {
if (head.val < mid.val) {
leftTail.next = head;
leftTail = head;
} else if (head.val > mid.val) {
rightTail.next = head;
rightTail = head;
} else {
middleTail.next = head;
middleTail = head;
}
head = head.next;
}
// 确保每一轮切分后，新的部分到切分点结束,这个地方若不写，则会出现超时，因为不写 null 指针，每一轮递归问题的规模不会下降
leftTail.next = null;
middleTail.next = null;
rightTail.next = null;
// 递归
ListNode left = sortList(leftDummy.next);
ListNode right = sortList(rightDummy.next);
return concat(left, middleDummy.next, right);
}
private ListNode findMedian(ListNode head) {
ListNode slow = head, fast = head.next;
// 比较有意思的是，fast.next != null 写到 fast != null 前面会出现空指针溢出错误
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 把三部分链表拼起来
private ListNode concat(ListNode left, ListNode middle, ListNode right) {
ListNode dummy = new ListNode(0), tail = dummy;
tail.next = left; tail = getTail(tail);
// 下一个 tail 是 left 的最后一个非空结点，形参的 middle 对应的传入值是middleDummy.next
tail.next = middle; tail = getTail(tail);
// 下一个 tail 是 middle 的最后一个非空结点
tail.next = right;
// 可写可不写的一句
tail = getTail(tail);
return dummy.next;
}
// 一个接一个地找到链表中的非空结点，遍历它们，然后返回每一部分最后一个非空结点
private ListNode getTail(ListNode head) {
if (head == null) {
return null;
}
while (head.next != null) {
head = head.next;
}
return head;
}
}
最后这个地方如果这么写，括号里写 left，middle，right 和写成 tail 实际上差了一个结点，若这么写，
比如：输入2 -> -1 -> 0 -> null，left == null，tail = getTail(left) 会返回 null 使得 tail 指向 null，空指针后面就没办法继续连接 middle 和 right 部分了；但如果是 tail = getTail(tail)，tail 是 dummy 结点，沿 tail.next = left 计算时尽管 left 等于空仍旧返回 dummy (非空结点)，仍可以继续进行； middle 和 right 为空的情形也是同理，这种写法保证了连接过程中不会出现连接 null 的错误
错误
- Quick Sort 2
相比于另一种快排省略了连接的过程，两种快排的区别主要在于右边切分部分的头结点位置，本算法在链表最结尾，另一种算法在分割好的右链表的开始结点
// 用pair来代表左右两个链表的分割点
class Pair {
public ListNode first, second;
public Pair(ListNode first, ListNode second) {
this.first = first;
this.second = second;
}
}
public class Solution {
/**
* @param head: The head of linked list.
* @return: You should return the head of the sorted linked list,
using constant space complexity.
*/
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMedian(head); // O(n)
// 注意这个地方时mid.val
Pair pair = partition(head, mid.val); // O(n)
// 递归传入的参数一定得是个变化的值，若是固定值，问题规模不见减小，会出现超时
ListNode left = sortList(pair.first);
ListNode right = sortList(pair.second);
// 把拆开的两行代码重新连起来
getTail(left).next = right; // O(n)
return left;
}
// 1->2->3 return 2
// 1->2 return 1
private ListNode findMedian(ListNode head) {
ListNode slow = head, fast = head.next;
// fast == null 代表只有一个结点，fast.next == null 代表只有两个结点，这种情况中值直接返回 slow 就可以了
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// < value in the left, > value in the right
private Pair partition(ListNode head, int value) {
ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
ListNode rightDummy = new ListNode(0), rightTail = rightDummy;
ListNode equalDummy = new ListNode(0), equalTail = equalDummy;
// 遍历链表将链表分为 3 部分
while (head != null) {
if (head.val < value) {
leftTail.next = head;
leftTail = head;
} else if (head.val > value) {
rightTail.next = head;
rightTail = head;
} else {
equalTail.next = head;
equalTail = head;
}
// 忘记这句 head 不继续往下移动就会出现超时
head = head.next;
}
leftTail.next = null;
rightTail.next = null;
equalTail.next = null;
// 只有链表中结点值全部一样时才会出现左边没结点，右边也没结点，这时找到 equal 的中间结点，左右各一半
if (leftDummy.next == null && rightDummy.next == null) {
ListNode mid = findMedian(equalDummy.next);
leftDummy.next = equalDummy.next;
rightDummy.next = mid.next;
mid.next = null;
// 之前选取的分割点是链表中最小的点，左边结点少，把中间结点全分给左边
// 尽量保证快速排序的时间平衡性
} else if (leftDummy.next == null) {
leftTail.next = equalDummy.next;
// 之前选取的分割点是链表中最大的点，右边结点少，把中间结点全分给右边
// 尽量保证快速排序的时间平衡性
} else {
rightTail.next = equalDummy.next;
}
// 尤其是在递归中，参数对应的值随时可变，要 deep copy 一下
return new Pair(leftDummy.next, rightDummy.next);
}
private ListNode getTail(ListNode head) {
if (head == null) {
return null;
}
// head.next == null 表明遍历到了链表最后一个结点，while 循环确保不返回null
while (head.next != null) {
head = head.next;
}
return head;
}
}
