一、题目
1、算法题目
“给定链表的头结点，返回按照升序排序的链表。”
2、题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1： 输入： head = [4,2,1,3] 输出： [1,2,3,4]
示例 2： 输入： head = [-1,5,3,4,0] 输出： [-1,0,3,4,5]
二、解题
1、思路分析
147题是实现链表的插入排序，时间复杂度是O(n2)。
这道题要求时间复杂度更低的排序算法，要求达到O(n log n)的时间复杂度。
可以实现O(n log n)的时间复杂度的排序算法有归并排序、堆排序和快速排序，其中最适合链表的排序算法是归并排序。
首先来了解一下什么是归并排序，归并排序是自顶向下直接合并的方式进行排序，具体过程如下：
- 1、找到链表中点，以中点为界，将链表拆成两个子链表。
- 2、对两个子链表分别排序。
- 3、将两个排序后子链表合并，得到完成链表。
因为上述的过程是通过递归实现的，所以时间复杂度为O(n log n)，空间复杂度为O(log n)。
2、代码实现
代码参考：
class Solution { public ListNode sortList(ListNode head) { return sortList(head, null); } public ListNode sortList(ListNode head, ListNode tail) { if (head == null) { return head; } if (head.next == tail) { head.next = null; return head; } ListNode slow = head, fast = head; while (fast != tail) { slow = slow.next; fast = fast.next; if (fast != tail) { fast = fast.next; } } ListNode mid = slow; ListNode list1 = sortList(head, mid); ListNode list2 = sortList(mid, tail); ListNode sorted = merge(list1, list2); return sorted; } public ListNode merge(ListNode head1, ListNode head2) { ListNode dummyHead = new ListNode(0); ListNode temp = dummyHead, temp1 = head1, temp2 = head2; while (temp1 != null && temp2 != null) { if (temp1.val <= temp2.val) { temp.next = temp1; temp1 = temp1.next; } else { temp.next = temp2; temp2 = temp2.next; } temp = temp.next; } if (temp1 != null) { temp.next = temp1; } else if (temp2 != null) { temp.next = temp2; } return dummyHead.next; } }
3、时间复杂度
时间复杂度：O(n log n)
其中n是链表的长度。
空间复杂度：O(log n)
其中n是链表的长度，空间复杂度主要取决于递归调用的栈空间。
三、总结
通过递归实现链表的归并排序，主要分成两步。
第一步是分割成两个子链表。
可以使用快慢指针，快指针每次移动2步，慢指针每次移动1步，当快指针移动到链表末尾时，慢指针指向链表的节点就是链表的中点。
第二步是子链表递归分别排序。
设置两个指针分别指向两个链表头部，比较两个指针处节点值大小，由小到大加入合并到链表头部，指针交替前进，直到添加完两个链表。
