「这是我参与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
}
复制代码
近期评论