关于java:排序链表LeetCode148

题目形容

在 O(nlogn) 工夫复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输出: 4->2->1->3
输入: 1->2->3->4

崩溃思路

一、递归归并排序
1、应用快慢指针在两头节点将链表 cut；
2、应用左右节点对 cut 后的链表进行递归 cut;
3、递归终止条件：listnode.next = null;
4、对合成后的链表进行递归 merge

二、链表转数组再回填（空间复杂度 n，工夫复杂度 nlogn）

1、将链表数据填入数组
2、对数组排序
3、将数值从新写入链表

语言积攒

1、应用快慢指针疾速查找链表的两头节点，须要留神对尾节点的判空，快慢指针在同一终点和快指针的初始地位在满指针的后面一个地位，有点区别
2、对数组递归 cut 的时候，留神递归的写法
3、递归 merge 的时候，返回节点及造成链表的形式有点意思
```
left.next = mergeList(left.next, right);
        return left;

### vscode 代码链接
[https://github.com/lunaDolphin/leetcode/tree/master/queue_linkedList_sortList_148](https://github.com/lunaDolphin/leetcode/tree/master/queue_linkedList_sortList_148)
[https://github.com/lunaDolphin/leetcode/tree/master/queue_linkedList_sortList_148_1](https://github.com/lunaDolphin/leetcode/tree/master/queue_linkedList_sortList_148_1)