题目描述
head进阶：
O(n log n)示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
[0, 5 * 104]-105 <= Node.val <= 105算法
本题的要求是在常数级空间，那么就不能将数组读取出来，排序然后构建新的链表，所以我们需要直接在本链表上面做出修改，修改链表的结点之间的指针，从而对数组重新排序
我们采用的思路是归并排序，首先是两个结点之间排序组成一个长度为2的有序链表，然后是两个长度为2的有序链表排序组成一个长度为4的有序链表
- 设置步长为1
- 按照步长取子链表，每次取两个子链表，将他们结合成一个新的链表
- 当整个链表都取完了以后，将步长乘以2，得到新的步长，继续上面的步骤
- 当步长大于或者等于链表的长度的时候，整个链表就是一个有序的链表了
代码
func sortList(head *ListNode) *ListNode {
if head == nil {
return nil
}
tmp := head
length := 0
for tmp != nil {
length++
tmp = tmp.Next
}
// 自底向上的归并
preHead := &ListNode{}
// preHead.Next = head
step := 1
tmpHead := head
preLast, curFirst := preHead, preHead
for step <= length {
// 找出两个链表
list1 := tmpHead
for i := 0; i < step; i++ {
if tmpHead != nil {
tmpHead = tmpHead.Next
}
}
list2 := tmpHead
for i := 0; i < step; i++ {
if tmpHead != nil {
tmpHead = tmpHead.Next
}
}
// 然后对两个链表进行排序
var subHead *ListNode
count1, count2 := 0, 0
for {
if subHead == nil {
subHead = preLast
}
if list1 != nil && list2 != nil {
if list1.Val <= list2.Val {
subHead.Next = list1
curFirst = list1
subHead = subHead.Next
count1++
if count1 == step {
list1 = nil
} else {
list1 = list1.Next
}
} else {
subHead.Next = list2
curFirst = list2
subHead = subHead.Next
count2++
if count2 == step {
list2 = nil
} else {
list2 = list2.Next
}
}
} else if list1 != nil && list2 == nil {
subHead.Next = list1
curFirst = list1
subHead = subHead.Next
count1++
if count1 == step {
list1 = nil
} else {
list1 = list1.Next
}
} else if list1 == nil && list2 != nil {
subHead.Next = list2
curFirst = list2
subHead = subHead.Next
count2++
if count2 == step {
list2 = nil
} else {
list2 = list2.Next
}
} else {
preLast = curFirst
break
}
}
if tmpHead == nil {
step *= 2
tmpHead = preHead.Next
preLast = preHead
node := preHead.Next
for i := 0; i < length-1; i++ {
node = node.Next
}
node.Next = nil
}
}
return preHead.Next
}