在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
思路：时间复杂度的排序算法有归并排序、堆排序、快速排序等，使用归并排序来解答。
package leetcode
//在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
//示例 1:
//输入: 4->2->1->3
//输出: 1->2->3->4
//示例 2:
//输入: -1->5->3->4->0
//输出: -1->0->3->4->5
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 找出中点链表一分为二
p1 := head
p2 := head.Next
for {
if p2 == nil {
break
}
p2 = p2.Next
if p2 == nil {
break
}
p2 = p2.Next
p1 = p1.Next
}
p2 = p1.Next
p1.Next = nil
p1 = head
// 排序左边
p1 = sortList(p1)
// 排序右边
p2 = sortList(p2)
// 合并
p1 = mergeTwoLists(p1, p2)
return p1
}
func mergeTwoLists(left, right *ListNode) *ListNode {
if left == nil {
return right
}
if right == nil {
return left
}
if left.Val <= right.Val {
left.Next = mergeTwoLists(left.Next, right)
return left
} else {
right.Next = mergeTwoLists(left, right.Next)
return right
}
}
