排序链表

题目描述：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
通过次数159,543提交次数237,674

思路:

用归并排序，用递归写更加简洁易懂一些

代码:

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	fast, slow := head, head
	var pre *ListNode
    //用快慢指针
	for fast != nil && fast.Next != nil {

		pre = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	pre.Next = nil
	l := sortList(head)
	r := sortList(slow)
	return mergeList(l, r)
}
func mergeList(l, r *ListNode) *ListNode {
    //制造头节点方便操作
	head := &ListNode{Val: 0}
	pre := head
	for l != nil && r != nil {
		if l.Val > r.Val {
			pre.Next = r
			r = r.Next
		} else {
			pre.Next = l
			l = l.Next
		}
		pre = pre.Next
	}
	if l != nil {
		pre.Next = l
	}
	if r != nil {
		pre.Next = r
	}
    //这才是真正的开始
	return head.Next
}

代码效率：

执行用时：32 ms, 在所有 Go 提交中击败了91.30%的用户
内存消耗：7.1 MB, 在所有 Go 提交中击败了90.61%的用户