本文共 274 字，大约阅读时间需要 1 分钟。

一个常规的链表排序算法，需要 O(n log n) 的时间复杂度与常数空间复杂度，一般采用归并排序的思想。

归并排序的核心原理在于将链表分成若干小段进行排序，然后再将这些已经排序的小段按顺序归并成最终的排序链表。这种方法天然地支持 O(n log n) 的时间复杂度。

第一步，可以通过快慢指针找到链表的中点节点。左右半段的链表分别进行递归排序后，然后将两个有序链表进行归并。

合并过程中，可以用一个辅助链表的头节点逐步将两条链表的节点连接起来，根据节点的值大小决定连接顺序。

这个方法不仅时间复杂度优越，在实现上也非常高效，适用于各种长度的链表。

转载地址：http://gtgyk.baihongyu.com/