题解 | #单链表的排序#

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

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
*/
func sortInList( head *ListNode ) *ListNode {
    // write code here    
    // 归并排序
    if head == nil || head.Next == nil {
        return head
    }
    
    mid := middle(head)
    l2 := sortInList(mid.Next)
    mid.Next = nil
    l1 := sortInList(head)
    
    return merge(l1,l2)
    
}

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

func merge(l1,l2 *ListNode) *ListNode {
    root := &ListNode{}
    r := root
    
    h1,h2 := l1,l2
    for h1 != nil && h2 != nil {
        if h1.Val < h2.Val {
            r.Next = h1
            h1 = h1.Next
        }else{
            r.Next = h2
            h2 = h2.Next
        }
        r = r.Next
    }
    
    if h1 != nil {
        r.Next = h1
    }
    
    if h2 != nil {
        r.Next = h2
    }
    
    return root.Next
}