本次刷题日记的第 69 篇,力扣题为:剑指 Offer II 029. 排序的循环链表,中等
一、题目描述:
剑指 Offer II 029. 排序的循环链表,看下是需要我们如何去给链表排序
二、这道题考察了什么思想?你的思路是什么?
剑指 Offer II 029. 排序的循环链表,看着题目文字挺长,仔细看看都讲了哪些重点信息:
- 题目给出了咱们一个循环链表,示例上是按照数组的方式来进行展示的,链表中的节点数据是整型
- 题目给出一个数字,需要我们将数字做成节点插入到循环链表中,插入前和插入后,始终需要保持整个链表是一个升序的循环链表
分析
做这个题,第一要知道什么是链表,再着,要知道啥是循环链表,以及链表的基本操作需要知道如何去处理
那什么是链表?
简单来说就是,存储空间不连续,通过指针连接多个节点的数据结构,就是链表了,就像这样
链表的节点中,又包含数据域,指针域,例如这样
当然,每个节点都有自己的地址,上一个节点的指针域就是指向下一个节点的地址
到此,我们知道什么是链表了
那么什么是循环链表?
循环链表,自然也是属于链表的一种,简单来说,就是遍历循环链表,例如从 a 节点开始遍历,你能够再次回到 a 节点,那么他就是一个循环链表,即 有一个环
开始思考如何将节点插入到循环链表中来呢?
先要明白如何插入节点到链表中 , 插入节点的话,我们需要考虑,节点插入的位置
例如有这样的一个链表和待插入的节点
- 插入链表头
直接将待插入的节点指向链表头即可
- 链表中间
现将待插入节点指向当前节点的 下一个节点的地址
再将当前节点的指针指向待插入的节点
- 链表尾巴
直接将链表的尾巴节点,指向待插入节点即可
至此,你已经知道如何将节点插入到链表中了,那么如何插入到循环链表中,那也是一样的,目前为止已经没有盲点了
查询循环链表的话,我们更多的是要分析清楚需要插入节点的插入位置,当找到需要插入的位置,那么处理起来就是和上述一毛一样的:
分析节点插入的位置,还是和上述情况类似,目前要考虑实际情况
- 插入链表头
- 插入链表尾巴
对于循环链表来说,插入链表头,和插入链表尾,其实是一个意思,咱们这里直接插入尾巴即可
- 当校验当前题目需要插入数据到链表尾巴的有 2 种情况
- 当题目给出的链表为空的时候,其实是需要我们将创建的节点,指向咱们自己即可
- 当链表只有 1 个节点的时候,咱们只需要将链表头节点,指向我们待插入的节点即可
- 插入链表中间
那么待插入节点要插入到链表中间的话,很明确,链表当前的节点数一定是 大于等于 2 的
咱们的插入动作是一样的,但是我们需要考虑到业务情况
插入的节点数据 > 当前节点的数据 and 插入的节点数据 < 下一个节点的数据插入的节点数据 > 当前节点的数据 and 插入的节点数据 < 下一个节点的数据 插入的节点数据>当前节点的数据and插入的节点数据<下一个节点的数据
这种情况下就譬如 [1,3] 中间插入 2 , 满足这种情况,那么就需要插入
当前节点的数据 > 下一个节点的数据当前节点的数据 > 下一个节点的数据 当前节点的数据>下一个节点的数据
当处于这种情况的时候,我们就需要考虑这种情况,例如 [4,1] , 咱们可以在中间插入 5 或者 0
按照逻辑来看就是,基于上述的条件,还应满足如下条件,那么就需要插入
待插入节点的数据 > 当前节点数据 or 插入的节点数据 > 下一个节点的数据待插入节点的数据 > 当前节点数据 or 插入的节点数据 > 下一个节点的数据 待插入节点的数据>当前节点数据or插入的节点数据>下一个节点的数据
那么接下来就是按照上述逻辑实现代码的了,很简单吧
三、编码
根据上述逻辑和分析,我们就可以翻译成如下代码
此处需要考虑好几种情况
- 原链表为空
- 原链表只有 1 个元素
- 原链表有 多个元素,我们需要插入到中间
- 插入的数据 左小右大的情况
- 插入的数据 左大右小的情况, 且大于大的, 或者 小于小的
编码如下:
/** * Definition for a Node. * type Node struct { * Val int * Next *Node * } */ func insert(aNode *Node, x int) *Node { node := &Node{Val:x, Next:nil} // 题目给出的是空链表的时候 if aNode == nil { node.Next = node return node } // 题目给出的链表只有 1 个节点 if aNode.Next == aNode { aNode.Next = node node.Next = aNode return aNode } // 题目给出的链表有大于等于 2 个节点 curN, nextN := aNode, aNode.Next for nextN != aNode { // 如果 x 要插入 左小右大的情况 if x >= curN.Val && x <= nextN.Val { break } // 当要插入到左大右小的时候 if curN.Val > nextN.Val { // 若 x 大于大的, 或者 小于小的 if x >= curN.Val || x <= nextN.Val { break } } curN = curN.Next nextN = nextN.Next } curN.Next = node node.Next = nextN return aNode }
四、总结:
看到这里,相信做起来肯定很简单吧,咱们这种方式来实现,时间复杂度为 O(n) , 因为需要遍历给出的链表,最差的情况下全部遍历完
空间复杂度是 O(1)
今天就到这里,学习所得,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~