1.问题描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
2.难度等级
Medium。
3.热门指数
★★★★☆
4.解题思路
可参考归并排序中的归并排序思想，主要有三个步骤。
- 找到链表的中间结点。
寻找链表的中点可以使用快慢指针的做法，快指针每次移动 222 步，慢指针每次移动 111 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
递归对左半部分和右半部分排序。
将两个排序后的子链表合并，得到完整的排序后的链表。
可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
时间复杂度： O(nlogn)。
空间复杂度： 递归栈空间复杂度为 O(logn)，不考虑的话为 O(1)。
下面以 Golang 为例给出实现。
func merge(head1, head2 *ListNode) *ListNode {
dummyHead := &ListNode{
}
temp, temp1, temp2 := dummyHead, head1, head2
for temp1 != nil && temp2 != nil {
if temp1.Val < temp2.Val {
temp.Next = temp1
temp1 = temp1.Next
} else {
temp.Next = temp2
temp2 = temp2.Next
}
temp = temp.Next
}
if temp1 != nil {
temp.Next = temp1
} else {
temp.Next = temp2
}
return dummyHead.Next
}
func findmid(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
dummy := &ListNode{
Next: head,
}
slow, fast := dummy, dummy
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func mergesort(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
mid := findmid(head)
rhead := mid.Next
mid.Next = nil
// 排序左链表
l := mergesort(head)
// 排序右链表
r := mergesort(rhead)
// 合并左右链表
return merge(l, r)
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
return mergesort(head)
}
