目录
- 基本性质
-
链表的分类
- 按连接方向分类
- 按照有无循环分类
- 链表问题代码实现的关键点
- 链表插入和删除的注意事项
- 链表翻转
- 向一个有序的环境链表中插入一个节点，并保持依旧有序
- 对于一个单链表，在不给定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)
}
}
