排序链表_LeetCode_148

题目描述

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

评论

暂无评论