高频算法面试题（二十八）-单链表的排序

「这是我参与11月更文挑战的第 14 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

单链表的排序

题目来源：LeetCode-148. 排序链表

题目描述

给你链表的头结点 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 = []
输出：[]
复制代码

提示：

解题

解法一：暴力解法

思路

首先看到是排序，我们肯定就想到那八大排序算法，但是因为要排序的是链表，就很难用那八大排序算法了，因为链表不支持根据下标随机访问

不能使用就想办法使用，把链表遍历一遍，把值取出来放到一个数组中，然后对数组中的元素进行排序。之后再按顺序将排序后的数组元素，连接成一个链表

暴力解法思路很简单，如果用快排，它的时间复杂度是O(nlog)，因为需要一个新的链表，所以需要额外的空间，空间复杂度是链表元素的个数，也就是o(n)

这里就不放代码了，主要看下边这种排序方法

解法二：归并排序

思路

有人一看到归并排序，可能就想到它的空间复杂度并不是O(1)，但是我们要排的元素是存在链表里的，不是数组，我们可以在O(1)的空间复杂度，实现两个链表的合并

归并排序本质上是一种分治思想，本题就是将链表不断的一分为二，当链表分到一定程度的时候，就只剩一个结点的时候，那它就是有序的，那再将有序链表合并，最后这个链表不就是有序的了吗？

归并排序主要是找中间位置，链表找中间位置很简单，用快慢指针。慢指针，一次移动一个结点，快指针一次移动两个节点，当快指针到达链表的尾部的时候，慢指针的位置就是链表的中点位置

不清楚归并排序过程的，可以看这里（有图）

代码

//链表排序
func sortList(head *ListNode) *ListNode {
	return Sort(head, nil)
}

func Sort(head, tail *ListNode) *ListNode {
	if head == nil {
		return head
	}
	if head.Next == tail {
		head.Next = nil
		return head
	}
	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}
	mid := slow

	return MergeList(Sort(head, mid), Sort(mid, tail))
}

func MergeList(head1, head2 *ListNode) *ListNode {
	dummy := &ListNode{} // 哨兵头结点
	tmpNode, tmpNode1, tmpNode2 := dummy, head1, head2
	for tmpNode1 != nil && tmpNode2 != nil {
		if tmpNode1.Val <= tmpNode2.Val {
			tmpNode.Next = tmpNode1
			tmpNode1 = tmpNode1.Next
		} else {
			tmpNode.Next = tmpNode2
			tmpNode2 = tmpNode2.Next
		}

		tmpNode = tmpNode.Next
	}

	if tmpNode1 != nil {
		tmpNode.Next = tmpNode1
	}
	if tmpNode2 != nil {
		tmpNode.Next = tmpNode2
	}

	return dummy.Next
}
复制代码