题目描述#

给定一个链表的头节点 head，要求把链表按照 升序 排列，并返回排序后的新头节点。

进阶要求是时间复杂度 O(n log n)，并且尽量使用常数级额外空间。

思路#

链表不像数组能随机访问下标，所以适合数组的快排在链表上写起来不优雅。这里用 归并排序：分治三步走——把链表对半切，分别递归排序两半，再把两条有序链表合并起来。

第一步是 找中点。经典做法是快慢指针：fast 每次走两步、slow 每次走一步，当 fast 走到末尾时，slow 正好停在中间。这里的小技巧是让 fast 从 head.Next 起跑而不是 head，这样在偶数长度时 slow 会停在前半段的最后一个节点，刚好可以让 mid := slow.Next 作为右半边的起点；同时把 slow.Next 置 nil，左半边就有了独立的结尾，两段链表彻底断开。如果 fast 也从 head 起跑，奇数长度下 slow 会落在正中间，反而要多写判断。

第二步是 递归：sortList(head) 排好左半，sortList(mid) 排好右半。递归的终止条件是 head == nil || head.Next == nil，也就是空链表或单节点直接视为已排序。

第三步是 合并两条有序链表：写一个 merge 函数，开一个 dummy 哨兵节点，用 cur 维护尾指针，比较 left 和 right 当前节点谁小就把谁挂到 cur.Next，并让被选中的链表前进一步、cur 也跟着前进。某一边走完之后，把另一边剩余的整段直接接到 cur.Next 即可——链表的好处就在这儿，剩下的尾巴不用一个个挪。

时间复杂度是 O(n log n)：log n 层递归，每层合并一共要看 n 个节点。空间复杂度上，虽然合并本身是原地操作没有新建节点，但递归栈深度是 O(log n)，所以严格说还不是常数空间。要做到 O(1) 额外空间得改成自底向上的迭代归并，这里递归版本读起来更舒服。本姑娘觉得分治写起来就像把照片切成一摞小卡片，每张排好再咔嚓拼回去～

思维边界#

• 递归出口：head == nil 处理外部传入空链表；head.Next == nil 处理递归切到底的情况，两种都直接返回当前指针。
• 快慢指针的起跑线：让 fast 从 head.Next 出发，可以保证偶数节点时 slow 落在前半段末尾，便于 mid := slow.Next 取右半的头并断开。
• 断链很关键：忘记 slow.Next = nil 会让左半段一直串到右半段，递归就跑不出来了。
• 合并的尾接：当一侧已经走空时，另一侧本身就是有序的，直接 cur.Next = left/right 把整段挂上去，不要再继续逐节点挪。
• 比较运算符的稳定性：使用 left.Val < right.Val，相等时优先取右边，归并排序整体仍是稳定的；不会影响正确性。
• 空间复杂度的代价：递归实现需要 O(log n) 栈空间；如果题目卡常数空间，可以改成自底向上的迭代归并，每轮按窗口长度 1, 2, 4, ... 合并相邻段。

代码#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 我们需要使用快慢指针查找链表的中间节点
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	mid := slow.Next
	slow.Next = nil

	// 我们有head 和 mid
	left := sortList(head)
	right := sortList(mid)

	return merge(left, right)
}

func merge(left, right *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for left != nil && right != nil {
		if left.Val < right.Val {
			cur.Next = left
			left = left.Next
		} else {
			cur.Next = right
			right = right.Next
		}
		// 注意这里cur需要后移动
		cur = cur.Next
	}
	if left != nil {
		cur.Next = left
	} else if right != nil {
		cur.Next = right
	}
	return dummy.Next
}