目录 https://www.jianshu.com/p/efa51c027e64
基本性质
链表的分类
按连接方向分类
按照有无循环分类
链表问题代码实现的关键点
链表插入和删除的注意事项
链表翻转
向一个有序的环境链表中插入一个节点, 并保持依旧有序
对于一个单链表, 在不给定 head 的情况下删除指定 node. 要求时间复杂度 O(1)
给定一个链表, 与一个数组 num. 要求实现荷兰国旗
给定两个有序链表的 head, 打印共同部分
给定一个单链表的 head, 实现一个调整链表的函数, 使得每 K 个节点之间逆序, 如果最后不足 K 个, 则不调整
判断一个链表是否为回文结构
判断一个单链表是否有环, 如有则返回入环节点. 时间复杂度 O(N), 额外空间复杂度 O(1)
两个无环单链表是否相交, 时间复杂度 O(N+M), 额外空间复杂度 O(1)
判断两个有环单链表是否相交, 时间复杂度 O(N+M), 额外空间复杂度 O(1)
判断两个链表是否相交, 并返回第一个相交的节点
基本性质
链表问题算法难度不高, 但考察代码的实现能力
链表和数组一样, 都是一种线性结构
数组是物理地址上一段连续的存储空间. 可以通过下标直接获取元素 当内容超出容量时需要重新定义数组.
链表空间不一定保持联系, 为临时分配的. 只能从链表的头部开始一个一个查找 增删的效率高于数组, 因为不需要更改内存结构
链表的分类
按连接方向分类
单链表 每个节点只能通过 next 指针, 指向下一个节点.
双链表 除了 next 指针之外, 还有一个 prev 指针指向其上一个节点.
按照有无循环分类
普通链表 头无 prev, 尾无 next.
循环链表 首尾相接的链表. 最后一个节点的 next 指针指向其第一个节点 对于双链表, 其第一个节点的 prev 指针指向最后一个节点.
链表问题代码实现的关键点
链表调整函数的返回值, 往往是节点类型
链表在调整过程中往往遇到改变头部的情况, 如果头节点被改变则需要返回一个新头部.
在调整链表的过程中, 先采用画图的方式理清逻辑
注意那些指针变化了, 同时注意对前后节点的影响.
边界条件的处理
头节点, 尾节点, 空节点的特殊处理.
链表插入和删除的注意事项
特殊处理链表为空或长度为 1
插入过程的调整
取得前后节点, 将前节点的 next 指向新节点, 新节点的 next 指向后节点.
删除过程的调整
取得前后节点, 将前一个节点的 next 指针指向后一个节点.
头尾插入或删除
在逻辑的设计上应该考虑空节点的情况
链表翻转
特殊处理链表为空或长度为 1
单链表的翻转
已翻转的头节点 head, 下一个节点 now
将 now 节点的 next 指向 head
将 now 节点设置为已翻转部分的新 head
需要注意在执行 1,2 步骤之前需要一个变量来储存原 now 节点的 next 节点. 步骤 2 设置了新的 head 之后, 将该节点作为新的 now, 继续翻转.
向一个有序的环境链表中插入一个节点, 并保持依旧有序.
要求时间复杂度 O(N), 额外空间复杂度 O(1).
如果链表为空
让新节点 node 自己成为环形链表, 并返回 node 即可.
如果链表不为空
令变量 prve 设为头节点, current 设为第二个节点, 两个节点同步移动.
当有 node<=prve && node>=current, 则说明 node 应该插入二者之间
若 prve 回到 head 但依旧没有合适的位置插入 说明 node 为最大值或最小值, 插入 head 之前即可. 需要区分为两种情况下是否出现新的 head, 并返回.
对于一个单链表, 在不给定 head 的情况下删除指定 node. 要求时间复杂度 O(1)
如果 node.next 不为空, 也就是 node 不是尾节点
如果工程允许, 可以将 node.next 的内容 copy 到 node 节点上, 变相的删除了 node 节点的数据.
如果 node 是尾节点
无法删除
给定一个链表, 与一个数组 num. 要求实现荷兰国旗
将链表遍历成数组, 然后进行荷兰国旗排序, 最后还原成链表.
遍历链表的过程中使用三个小链表. 小于, 等于, 大于. 最后将三个链表串联.
给定两个有序链表的 head, 打印共同部分
有一个为空直接返回
采用外排的方式, 直到有一个为空则停止.
给定一个单链表的 head, 实现一个调整链表的函数, 使得每 K 个节点之间逆序, 如果最后不足 K 个, 则不调整.
链表为空, 长度 < k 或者 k<2 直接返回
通过栈结构, 实现逆序
需要保留上次逆序的最后一位元素, 修改其 next.
最后段不足 k 个, 直接不修改. 值将上次逆序的最后一个元素 next 设置好.
第一组的第一个节点为头节点.
不使用栈结构, 手动逆序
判断一个链表是否为回文结构
将链表节点依次入栈, 在弹出时与原链表依次比对.
使用快行指针, 通过二倍速的方式遍历. 依次将慢指针的节点压入栈中, 当快节点遍历到末尾时, 慢指针正好处于中间位置. 继续移动慢指针, 并与栈中弹出的元素做对比.(需要注意总量的奇偶)
将后半部分链表进行逆序处理, 从两端同时进行遍历比对
判断一个单链表是否有环, 如有则返回入环节点. 时间复杂度 O(N), 额外空间复杂度 O(1)
- #1. 如果链表有结尾, 则说明无环
- #2.1 如果不要求额外空间复杂度, 可以直接用哈希表比对.
- #2.2 使用快行指针的方式
如果两指针相遇则表示有环, 此时将快指针改为 1, 并从 head 重新同步移动, 相遇处即为入环位置或者还有另一个证明.
- # 代码
- /// 获取入环节点
- ///
- /// - Parameter node: 头节点
- /// - Returns: 有环则返回入环节点, 否则返回空
- func getLoopNode(head : Node) -> Node {
- // 链表长度为 0,1,2 不可能成环
- if head==nil || head.next==nil || head.next.next==nil {
- return nil
- }
- var slowP = head // 慢行指针
- var fastP = head // 快行指针
- while slowP != fastP {
- if slowP.next==nil || fastP.next.next==nil { // 链表有结尾, 不可能成环
- return nil
- }
- slowP = slowP.next
- fastP = fastP.next.next
- }// 运行到这里说明两指针相遇了
- // 从 head 开始遍历再次相交则为入环点
- fastP = head
- while fastP != slowP {
- slowP = slowP.next
- fastP = fastP.next
- }
- return fastP
- }
两个无环单链表是否相交, 时间复杂度 O(N+M), 额外空间复杂度 O(1)
- #1. 先遍历两个链表确定长度
- #2. 若两个链表结尾不同, 则不相交
- #3. 另长链表从短链表开始位置与短链表再次同步遍历, 查看是否相同.
- # 代码
- /// 两个无环单链表是否相交
- ///
- /// - Parameters:
- /// - head1: 链表 1
- /// - head2: 链表 2
- /// - Returns: 相交点或者为空
- func noLoop(head1:Node ,head2:Node) -> Node {
- if head1==nil || head2==nil {
- return nil
- }
- var p1 = head1
- var p2 = head2
- // 获取两个链表长度差值
- var n = 0
- while p1.next != nil {
- p1 = p1.next
- n+=1
- }
- while p2.next != nil {
- p2 = p2.next
- n-=1
- }
- if p1 != p2 { // 若两个链表结尾不同, 则一定不相交
- return nil
- }
- p1 = n>=0 ? head1:head2 // 使 p1 指向较长的链表
- p2 = p2==head1 ? head2:head1 // 使 p2 指向另一个链表
- n = abs(n) // 取绝对值
- while n>0 {// 将长链表移动 n 次.
- p1 = p1.next
- n-=1
- }
- // 查找链表上第一个相同的点
- while p1 != p2 {
- p1 = p1.next
- p2 = p2.next
- }
- return p1
- }
判断两个有环单链表是否相交, 时间复杂度 O(N+M), 额外空间复杂度 O(1)
首先都需要先去定单独的入环节点, 然后
是否入环之前已经相交
是否入环时才相交, 则入环位置节点相同
如果相交点为 loop1 或者 loop2, 则为入环时才相交
入环后才相交 循环其中一个环, 若遇到另一个的入环节点则返回.
否则, 两链表并未相交
- # 代码
- /// 两个有环单链表是否相交
- ///
- /// - Parameters:
- /// - head1: 链表 1
- /// - head2: 链表 2
- /// - loop1: 链表 1 入环点
- /// - loop2: 链表 2 入环点
- /// - Returns: 相交点或者为空
- func bothLoop(head1:Node ,head2:Node ,loop1:Node ,loop2:Node) -> Node {
- if head1==nil || head2==nil{
- return nil
- }
- if loop1 == loop2 { // 两个链表在入环之前已经相交
- var p1 = head1
- var p2 = head2
- // 获取两个链表长度差值
- var n = 0
- while p1.next != loop1 {
- p1 = p1.next
- n+=1
- }
- while p2.next != loop2 {
- p2 = p2.next
- n-=1
- }
- p1 = n>=0 ? head1:head2 // 使 p1 指向较长的链表
- p2 = p2==head1 ? head2:head1 // 使 p2 指向另一个链表
- n = abs(n) // 取绝对值
- while n>0 {// 将长链表移动 n 次.
- p1 = p1.next
- n-=1
- }
- // 查找链表上第一个相同的点
- while p1 != p2 {
- p1 = p1.next
- p2 = p2.next
- }
- return p1
- }else { // 两个链表在入环之后才相交
- var p1 = loop1.next
- var p2 = loop2
- while p1 == loop1 { // 循环 loop1 一次
- p1 = p1.next
- if p1 == p2 {
- return p1
- }
- }
- return nil // 并未相交
- }
- }
判断两个链表是否相交, 并返回第一个相交的节点
尝试找到各自的入环节点
若一个有环一个无环, 则不相交
若都为无环, 则按照上文《两个无环单链表是否相交》的方式查找
若都为有环, 则按照上文《判断两个有环单链表是否相交》的方式查找
- # 代码
- func getIntersectNode(head1:Node,head2:Node) -> Node {
- if head1 == nil || head2 == nil {
- return nil
- }
- // 获取两个入环节点
- var loop1 = getLoopNode(head: head1)
- var loop2 = getLoopNode(head: head2)
- if (loop1 == nil && loop2 != nil)||(loop1 != nil && loop2==nil) {
- return nil // 一个有环一个无环, 肯定不相交
- }
- if loop1==nil || loop2==nil {// 两个链表都不为环型结构
- return noLoop(head1: head1, head2: head2)
- }else { // 两个环形链表
- return bothLoop(head1: head1, head2: head2, loop1: loop1, loop2: loop2)
- }
- }
参考资料
左神牛课网算法课 https://www.nowcoder.com/
来源: https://juejin.im/post/5c08fb3ff265da61483b6814