[LeetCode] 148. Sort List
原题链接: https://leetcode.com/problems/sort-list/
1. 题目介绍
Sort a linked list in O(n log n) time using constant space complexity.
使用常数级的空间复杂度 和 O(n log n) 的时间复杂度为一个链表排序。
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
2. 解题思路
题目中明确规定,时间复杂度必须为 O(n log n)。因此可以考虑快速排序,归并排序和堆排序。由于题目中的所使用的是单向链表而不是数组,所以最好的解决办法是归并排序。
2.1 理解归并排序
注: 本部分关于归并排序的介绍和图片,参考了 https://www.cnblogs.com/chengxiao/p/6194356.html ,有兴趣的读者可以直接去看原文。
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题 分(divide) 成一些小的问题然后递归求解,而 治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。
总的来说,先要进入分阶段,在这个阶段将链表不停地分成2个部分,分到什么时候为止呢,要分到这两部分都只有一个元素,此时这两部分肯定都是有序的了(因为只剩下1个元素,当然有序)。
然后进入治阶段,将两个已经有序的链表合并成一个有序的链表。
2.2 将链表从中间一分为二
在分治算法中,需要将链表从中间一分为二,该如何实现呢?
这个问题非常常见,LeetCode很多道题都遇到了如何将链表从中间一分为二、如何找到链表的中点的问题。对此的解决方法是:快慢双指针法。
设定一个快指针 fast,一个慢指针slow。两个指针一开始都在链表的头结点上。快指针每次走两步,慢指针每次走一步。当 fast 走到链表的末尾的时候, slow 就停在链表的中点了。于是可以据此将链表从slow指针所指的节点分开。
2.3 将两个有序链表合并为新的有序链表
使用两个指针A 、 B,分别指向两个有序链表的第一个节点。再新建一个指针C。随后比较A、B两个节点的值。假如 A.val 比较小,那么C就指向 A,然后A = A.next ,C = C.next. 就向这样一步一步向后走,C总是指向A、B中较小的那个。
当其中一个链表走完后,将另外链表剩下的元素全都放在C节点的后面,至此新的有序链表就排好了。
在代码实现的环节,我参考了 http://www.cnblogs.com/grandyang/p/4249905.html 的 Java 代码,有兴趣的读者可以直接去看原文。
实现代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
//将链表从中间分为两个部分
ListNode fast = head;
ListNode slow = head;
ListNode slowPre = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
slowPre = slow;
slow = slow.next;
}
slowPre.next = null;
//分开后,第一个链表从head开始,到slowPre结束
//第二个链表从slow开始,到链表结尾结束
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
//将两个有序的链表合并为一个有序链表
ListNode assist = new ListNode(0);
ListNode cur = assist;
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.next;
}
cur.next = (l1 == null ? l2 : l1);
return assist.next;
}
}
3. 参考资料
https://www.cnblogs.com/chengxiao/p/6194356.html
http://www.cnblogs.com/grandyang/p/4249905.html