题目描述
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
样例
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
算法1
(自底向上的归并排序),非递归,所以无额外空间,满足常数级空间复杂度
时间复杂度 o(nlogn)
golang 代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func merge(l, r *ListNode) *ListNode {
tmp := &ListNode{-1, nil}
h := tmp
for l != nil && r != nil {
if l.Val < r.Val {
tmp.Next = l
tmp = l
l = l.Next
} else {
tmp.Next = r
tmp = r
r = r.Next
}
}
if l != nil {
tmp.Next = l
} else if r != nil {
tmp.Next = r
}
return h.Next
}
func cut(l *ListNode, n int) *ListNode{
for n > 1 && l != nil {
l = l.Next
n --
}
if l != nil {
r := l.Next
l.Next = nil
return r
}
return nil
}
func sortList(head *ListNode) *ListNode {
var size int = 0
for p := head; p != nil; p = p.Next{
size ++
}
dummy := &ListNode{-1, head}
for i := 1; i <= size; i *= 2{
cur := dummy.Next
tail := dummy
for cur != nil {
l := cur
r := cut(l, i)
cur = cut(r, i)
tail.Next = merge(l, r)
for tail.Next != nil {
tail = tail.Next
}
}
}
return dummy.Next
}
啥语言?
golang