题解 | #牛群的身高排序#

知识点：

小顶堆

解题思路：

遍历链表，将其放入小顶堆排序，在依次pop出即可

语言：

Golang

package main

import "container/heap"

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
type MyHeap []*ListNode

func (h MyHeap) Less(a, b int) bool  { return h[a].Val < h[b].Val }
func (h MyHeap) Swap(a, b int)       { h[a], h[b] = h[b], h[a] }
func (h MyHeap) Len() int            { return len(h) }
func (h *MyHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *MyHeap) Pop() interface{} {
	n := len(*h)
	ans := (*h)[n-1]
	*h = (*h)[:n-1]
	return ans
}
func sortList(head *ListNode) *ListNode {
	// write code here
	h := MyHeap{}
	heap.Init(&h)
	cur := head
	for cur != nil {
		heap.Push(&h, cur)
		cur = cur.Next
	}
	newHead := &ListNode{}
	cur = newHead
	for len(h) > 0 {
		cur.Next = heap.Pop(&h).(*ListNode)
        cur = cur.Next
	}
	cur.Next =nil
	return newHead.Next
}