题解 | #单链表的排序#

package main
import . "nc_tools"

//时间nlogn， 空间O1
func sortInList( head *ListNode ) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    fast, slow := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    second_head := slow.Next
    slow.Next = nil
    l1, l2 := sortInList(head), sortInList(second_head)

    dummy := &ListNode{}
    pre := dummy                                    

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            pre.Next = l1
            l1 = l1.Next
        } else {
            pre.Next = l2
            l2 = l2.Next
        }
        pre = pre.Next
    }

    if l1 == nil {
        pre.Next = l2
    }
    if l2 == nil {
        pre.Next = l1
    }

    return dummy.Next
}