Sort a linked list inO(nlogn) time using constant space complexity.
解题思路：看到这个时间复杂度就能想到归并排序或者快速排序算法，这里我就用相对简单的归并排序解决，解决思路和数组的归并排序一致。
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
left, right := splitList(head)
return merge(sortList(left), sortList(right))
}
//用快慢指针从链表头部开始，找到中间位置进行拆分
func splitList(head *ListNode) (left, right *ListNode) {
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
//从slow这个中间节点断开
fast = slow
slow = slow.Next
fast.Next = nil
left, right = head, slow
return
}
func merge(left, right *ListNode) *ListNode {
node := &ListNode{}
//node会随着新节点的插入一直往后递增
head := node
for left != nil && right != nil {
if left.Val < right.Val {
node.Next, left = left, left.Next
} else {
node.Next, right = right, right.Next
}
node = node.Next
}
//如果只剩left或者right
if left != nil {
node.Next = left
} else {
node.Next = right
}
return head.Next
}
网友评论