在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下客蹋，對(duì)鏈表進(jìn)行排序盐捷。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
思路：時(shí)間復(fù)雜度的排序算法有歸并排序、堆排序辜腺、快速排序等休建，使用歸并排序來解答。
package leetcode
//在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下评疗，對(duì)鏈表進(jì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
}
// 找出中點(diǎn)鏈表一分為二
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
}
}
