在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表

摘自力扣题解，加了注释

func sortList(head *ListNode) *ListNode  {
    if head == nil {
        return head
    }

    // 获取List长度
    length := 0
    for node := head; node != nil; node = node.Next {
        length++
    }

    dummyHead := &ListNode{0, head}

    // 遍历直到subLength增长到length
    for subLength := 1; subLength < length; subLength <<= 1 {
        // 重置为开头
        prev, cur := dummyHead, dummyHead.Next

        // 每次两小段合并，直到走完
        for cur != nil {

            // 第一小段的开头是整个List的开头或者第二小段末尾的下一个
            head1 := cur
            // cur走完subLength-1个长度，找到第一小段的末尾
            for i := 1; i < subLength && cur.Next != nil; i++ {
                cur = cur.Next
            }

            // 第二小段的开头就是第一小段的末尾的下一个
            head2 := cur.Next
            // 一定要把第一小段的最后一个元素的下一个指向nil！！！
            cur.Next = nil

            // 找第二小段的末尾
            cur = head2
            for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
                cur = cur.Next
            }

            // cur如果为nil便表示这轮结束
            // 但是不为nil的话，cur为第二小段的最后一个元素，需要将它的下一个指向nil
            if cur != nil {
                next := cur.Next
                cur.Next = nil
                cur = next
            }

            // 把刚刚拆下来的两小段重新装回去
            prev.Next = merge(head1, head2)

            // 将prev移到合并后的链表的最后一个
            for prev.Next != nil {
                prev = prev.Next
                fm
            }

        }

    }
    return dummyHead.Next
}

func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    temp, temp1, temp2 := dummyHead, head1, head2
    for temp1 != nil && temp2 != nil {
        if temp1.Val <= temp2.Val {
            temp.Next = temp1
            temp1 = temp1.Next
        } else {
            temp.Next = temp2
            temp2 = temp2.Next
        }
        temp = temp.Next
    }
    if temp1 != nil {
        temp.Next = temp1
    }
    if temp2 != nil {
        temp.Next = temp2
    }
    return dummyHead.Next
}