012.排序链表

• 148.排序链表
  • 自顶向下归并排序
    • 时间复杂度：O(nlogn)
    • 空间复杂度：O(logn)
  • 自底向上归并排序
    • 时间复杂度：O(nlogn)
    • 空间复杂度：O(1)

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

时间复杂度是 O(nlog⁡n) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n^2)，其中最适合链表的排序算法是归并排序。

归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(log⁡n)。如果要达到 O(1) 的空间复杂度，则需要使用自底向上的实现方式。

排序链表 - 自顶向下归并排序

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	return sort(head)
}
 
func sort(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
 
	// 这里 fast 必要要取 head.Next
	// 否则链表长度为 2 时，fast 和 slow 都指向 head.Next，就无限循环了
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
 
	// slow is mid
	midPlusOne := slow.Next
	slow.Next = nil
 
	return merge(sort(head), sort(midPlusOne))
}
 
func merge(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	dummy := &ListNode{}
	cur := dummy
	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	}
	if l2 != nil {
		cur.Next = l2
	}
	return dummy.Next
}

排序链表 - 自底向上归并排序

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	n := getLen(head)
	if n <= 1 {
		return head
	}
	dummy := &ListNode{ Next: head }
	for subLen := 1; subLen < n; subLen <<= 1 {
		// 这里 cur 必要要取 dummy.Next, 而不是 head
		prev, cur := dummy, dummy.Next
		for cur != nil {
			l1 := cur
			for i := 1; i < subLen && cur.Next != nil; i++ {
				cur = cur.Next
			}
 
			l2 := cur.Next
			cur.Next = nil
			cur = l2
			for i := 1; i < subLen && cur != nil; i++ {
				cur = cur.Next
			}
 
			var next *ListNode
			if cur != nil {
				next = cur.Next
				cur.Next = nil
			}
			prev.Next = merge(l1, l2)
 
			for prev.Next != nil {
				prev = prev.Next
			}
 
			cur = next
		}
	}
 
	return dummy.Next
}
 
func getLen(head *ListNode) int {
	res := 0
	for head != nil {
		res++
		head = head.Next
	}
	return res
}
 
func merge(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	dummy := &ListNode{}
	cur := dummy
	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	}
	if l2 != nil {
		cur.Next = l2
	}
	return dummy.Next
}