单链表的排序

package main

import . "nc_tools"
import "sort"

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

/**
 *
 * @param head ListNode类 the head node
 * @return ListNode类
 */
type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func sortInList(head *ListNode) *ListNode {
    var nums IntSlice
    p := head
    for p != nil {
        nums = append(nums, p.Val)
        p = p.Next
    }
    p = head
    sort.Sort(nums)
    for _, n := range nums {
        p.Val = n
        p = p.Next
    }
    return head
}

解题思路：

• 转化成数组，对数组进行排序，再按照数组重新给链表中的元素赋值