排序链表_LeetCode_148 - HelloWorld开发者社区

题目描述

在 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;