题解 | #单链表的排序#

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
*/

// 可以改变节点值得算法
// 1.选择排序(N2)
func sortInList( head *ListNode ) *ListNode {
    for h := head; h.Next != nil; h = h.Next {
        min := h
        for p := h; p != nil; p = p.Next {
            if p.Val < min.Val {
                min = p
            }
        }
        tmp := min.Val
        min.Val = h.Val
        h.Val = tmp
    } 
    return head
}


// 不改变节点值的算法
// 1.插入排序(N2)
func sortInList( head *ListNode ) *ListNode {
    h := &ListNode{
        Next: head,
    }
    
    for p1 := head;p1.Next != nil; {
        done := false
        for p2 := h; p2 != p1;p2 = p2.Next {
            if p2.Next.Val > p1.Next.Val {
                s := p1.Next
                p1.Next = s.Next
                s.Next = p2.Next
                p2.Next = s
                done = true
                break
            }
        }
        if !done {
             p1 = p1.Next
        }
    }
    return h.Next
}

// 2.归并排序(logN)
func sortInList( head *ListNode ) *ListNode {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return head
    }
    
    m := middle(head)
    list2 := sortInList(m.Next)
    m.Next = nil
    list1 := sortInList(head)
    return merge(list1, list2)
}

func middle(head *ListNode) *ListNode {
    fast, slow := head, head
    for ;fast.Next != nil && fast.Next.Next != nil; {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func merge(list1, list2 *ListNode) *ListNode{
    h := &ListNode{}
    ret := h
    for ;list1 != nil && list2 != nil; {
        if list1.Val < list2.Val {
            h.Next = list1
            list1 = list1.Next
        } else {
            h.Next = list2
            list2 = list2.Next
        }
        h = h.Next
    }
    if list1 == nil {
        h.Next = list2
    }
    if list2 == nil {
        h.Next = list1
    }
    return ret.Next
}