牛客网高频算法题系列-BM12-单链表的排序

题目描述

描述

原题目见：BM12 单链表的排序

解法一：数组排序

首先判断如果链表为空或者只有一个结点，则不需要排序，直接返回原链表。

否则，使用额外空间进行排序，处理过程如下：

• 首先遍历链表，将所有结点值暂存在一个List中；

• 然后，使用库函数将List排序（也可以使用各种排序算法进行排序）；

• 最后，将排序后的结点值构造成新的链表并返回。

解法二：归并排序

使用递归的方式，将原链表排序，递归处理过程如下：

• 首先也是要判断如果链表为空或者只有一个结点，则不需要处理，直接返回原链表；

• 然后，使用快慢指针寻找链表的中点位置；

• 然后，递归调用分别排序中点左右的两个链表；

• 然后，将左右链表合并；

• 最后，返回合并后的链表。

代码

1.01^{365} ≈ 37.7834343329   

0.99^{365} ≈ 0.02551796445   

相信坚持的力量！