题目：给定一条单向链表，对链表进行排序并返回排序后的链表。约束：时间复杂度为 O(nlogn)， 并且需要原地操作，即空间复杂度为 O(1)。本篇经验将分享如何通过归并排序算法在约束条件下对单向链表进行排序，如下引用经验分享的是通过插入排序算法对单向链表排序，其时间复杂度为 O(n²)。 0Java如何对一条单向链表进行插入排序
工具/原料
1
Eclipse
2
JDK1.8
方法/步骤
1
图示，声明一个静态内部类，表示链表节点，用于构建一条链表结构。
2
实现归并排序算法，算法思想如下：1. 通过快慢指针获取待排序链表的中点。2. 分别对中点前后两部分链表进行排序，注意：前后两部分要进行断链处理。3. 将两部分排序好的链表合并为一个排序好的链表。
3
实现将两个有序链表合并为一个有序链表的函数，即归并函数。
4
编写一个函数，将链表结构转变为字符串，辅助本地测试。
5
编写本地测试主方法。
6
运行本地测试主方法，观察控制台输出，符合预期，本地测试通过。
7
平台提交算法，测试通过。
注意事项
和数组归并排序的归并函数不同，链表的归并函数无需额外空间，因此空间复杂度为 O(1)
上一篇：约瑟夫环_循环链表JAVA解答
下一篇：数据结构之单链接表操作详解