题解 | #单链表的排序#

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 {
    // 总体思想分治
    // 1、快慢指针找到中间节点
    // 2、分割原链表，此时需要注意如若要按照中间节点拆分，则需知道其前一个节点
    // 3、递归
    // 4、合并有序数组
    if head == nil || head.Next == nil {
        return head
    }

    prev, slow, fast := head, head, head
    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    prev.Next = nil 
    head1 := sortInList(head)
    head2 := sortInList(slow)
    return mergeTwoList(head1, head2)
}

func mergeTwoList(head1 *ListNode, head2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for head1 != nil && head2 != nil {
        if head1.Val < head2.Val {
            tail.Next = head1
            head1 = head1.Next
        } else {
            tail.Next = head2
            head2 = head2.Next
        }
        tail = tail.Next
    }
    if head1 != nil {
        tail.Next = head1 
    }
    if head2 != nil {
        tail.Next = head2
    }
    return dummy.Next    
}