刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/sort-list/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例 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

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

思路

最开始看到O(nlogn)时间复杂度，第一反应就是归并排序，但是后面跟着一个常数级空间复杂度。才发现问题没有那么简单。

最开始反应过来的思路就是

• 快慢指针找到中点，然后分别归并排序
• 递归继续快慢指针找中点分别归并
• 退出条件就是需要归并的链表仅有一个或者零个节点
  但是实际写了下，发现这样因为用到了递归，其空间开销在递归过程中达到了O(logn)。那么现在问题就是，如何在不递归的情况下完成拆分&归并

那么如何不递归呢？
其实这个思路上有点类似dfs和bfs，如图：

• dfs，就需要每层深度上预留辅助空间等待下层的返回
• bfs，则可以每一层都处理完再考虑下一层问题，代码上就可以重复利用辅助空间
  
  而这里所谓的自顶向下，就是由大到小拆解问题。自底向上，就是由小到大处理问题。

至此，上代码。细节就放到代码注释了。

代码

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

	length := 0
	for node := head; node != nil; node = node.Next {
		length++
	}

	veryHead := &ListNode{Next: head}
	// 从小到大逐步归并
	for subLength := 1; subLength < length; subLength *= 2 {
		// 这里now应该赋值veryHead.Next，不能赋值head，因为归并后可能改变
		pre, now := veryHead, veryHead.Next
		for now != nil {
			head1 := now
			// 这里now能再次进入循环就不会是nil，不用判断自身
			for i := 0; i < subLength-1 && now.Next != nil; i++ {
				now = now.Next
			}

			// 如果 now.Next 为nil，那就意味着第二条链是空的，第一条链可能够长也可能不够长，但是不重要
			head2 := now.Next
			now.Next = nil
			now = head2
			// 有可能now已经走到终点，所以需要判断自身是不是nil
			for i := 0; i < subLength-1 && now != nil && now.Next != nil; i++ {
				now = now.Next
			}

			// 记录尾部，如果已经是nil，那就应该退出循环了，也无需维护now了，next就保持nil就行
			var next *ListNode
			if now != nil {
				next = now.Next
				now.Next = nil
			}

			fmt.Printf("subLen: %d, head1: %v\n", subLength, head1.print())
			fmt.Printf("subLen: %d, head2: %v\n", subLength, head2.print())
			// 归并，拼接头
			pre.Next = merge(head1, head2)
			// 移动到尾部，拼接尾
			for pre.Next != nil {
				pre = pre.Next
			}
			now = next
		}
	}
	return veryHead.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
	} else if temp2 != nil {
		temp.Next = temp2
	}
	fmt.Printf("newHead: %v\n", dummyHead.Next.print())
	return dummyHead.Next
}

// 写代码时辅助观察调试的代码
func (l *ListNode) print() string {
	str := ""
	now := l
	for now != nil {
		str += fmt.Sprintf("%d", now.Val) + "->"
		now = now.Next
	}
	return str
}
type ListNode struct {
	Val  int
	Next *ListNode
}