题目
- 将一个链表实现排序，要求其时间复杂度为O(nlogn)空间复杂度为常数
- 举例：链表4->2->1->3排序后:1->2->3->4
解题思路
- 选取排序算法
- 首先，在数组中我们拥有的基本排序算法可多了，选择排序、插入排序、希尔排序(插入排序的变形)、快速排序、归并排序、堆排序等，其中选择排序、插入排序的时间复杂度都是O(n2)级别，希尔排序O(n1.5),快排、归并和堆排序时间复杂度是O(nlogn)。
- 然后在快排、归并和堆排序中，我们需要注意的是快排采取的是左右向中间靠拢的方式，而链表是单向，如果采取快排我们需要另外选取右侧往左索引的方式，很麻烦。
- 堆排序需要额外的空间，辅助空间理论是需要O(n+r),这不符合我们的要求
- 归并排序在数组中理论上也是需要O(n)的辅助空间，但是因为链表的特殊性，可以直接操作更改链表指针，不需要额外的空间，因此本题的思路是需要采取归并排序
- 归并排序实现
- 首先我们以二分的方式将链表为左右两部分，二分采用快慢双指针即可实现，具体的查看之前的一些leetcode即可
- 然后我们对左半部分和右半部分分别进行递归排序，当达到递归终止条件时返回上层，再分别将左半部分和右半部分进行链表合并返回给上层。
- 采用的思想即是原始的由上至下的归并方法，递归找到最底层然后进行两个链表归并再依次返回->归并->返回->归并，直到递归的起始条件返回完成整个过程，因为是二分递归也即是呈现为树形，递归需要调用的时间是O(logn)级别，在回退过程中因为涉及到遍历和合并过程，所以最终时间复杂度为O(nlogn)级别
源代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
private ListNode sortList(ListNode start, ListNode last) {
//第一个节点就是空或者下一个节点为空直接返回
if (start == null || start.next == null) return start;
//如果两个相等则表示此时将这个节点的next置空返回
if (start == last) {
start.next = null;
return start;
}
//获取链表中间节点
ListNode middle = getMiddle(start, last);
//获取链表中间的下一个节点
ListNode middleNext = middle.next;
//左侧链表排序
ListNode left = sortList(start, middle);
//右侧链表排序
ListNode right = sortList(middleNext, last);
ListNode result = mergeSort(left, right);
return result;
}
private ListNode mergeSort(ListNode first, ListNode second) {
ListNode front = new ListNode(0);
ListNode pre = front;//插入节点的前一个节点索引
while (first != null || second != null) {
if (first == null) {
pre.next = second;
break;
} else if (second == null) {
pre.next = first;
break;
} else {
if (first.val < second.val) {
pre.next = first;
first = first.next;
pre = pre.next;
} else {
pre.next = second;
second = second.next;
pre = pre.next;
}
}
}
return front.next;
}
private ListNode getMiddle(ListNode start, ListNode last) {
ListNode slow = start, fast = start;//快慢二指针获取中间节点
while (fast != last && fast.next != last) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
