数据结构基础 链表

目录

• 基本性质
• 链表的分类
  • 按连接方向分类
  • 按照有无循环分类
• 链表问题代码实现的关键点
• 链表插入和删除的注意事项
• 链表翻转
• 向一个有序的环境链表中插入一个节点，并保持依旧有序
• 对于一个单链表，在不给定head的情况下删除指定node。要求时间复杂度O(1)
• 给定一个链表，与一个数组num。要求实现荷兰国旗
• 给定两个有序链表的head，打印共同部分
• 给定一个单链表的head，实现一个调整链表的函数，使得每K个节点之间逆序，如果最后不足K个，则不调整
• 判断一个链表是否为回文结构
• 判断一个单链表是否有环，如有则返回入环节点。时间复杂度O(N)，额外空间复杂度O(1)
• 两个无环单链表是否相交，时间复杂度O(N+M)，额外空间复杂度O(1)
• 判断两个有环单链表是否相交，时间复杂度O(N+M)，额外空间复杂度O(1)
• 判断两个链表是否相交，并返回第一个相交的节点

基本性质

• 链表问题算法难度不高，但考察代码的实现能力

• 链表和数组一样，都是一种线性结构

1. 数组是物理地址上一段连续的存储空间。 可以通过下标直接获取元素 当内容超出容量时需要重新定义数组。
2. 链表空间不一定保持联系，为临时分配的。 只能从链表的头部开始一个一个查找 增删的效率高于数组，因为不需要更改内存结构

链表的分类

• 按连接方向分类

1. 单链表 每个节点只能通过 next指针 ，指向下一个节点。
2. 双链表 除了 next指针 之外，还有一个 prev指针 指向其上一个节点。

• 按照有无循环分类

1. 普通链表 头无prev，尾无next。

2. 循环链表 首尾相接的链表。 最后一个节点的next指针指向其第一个节点 对于双链表，其第一个节点的prev指针指向最后一个节点。

   

链表问题代码实现的关键点

• 链表调整函数的返回值，往往是节点类型

链表在调整过程中往往遇到改变头部的情况，如果头节点被改变则需要返回一个新头部。

• 在调整链表的过程中，先采用画图的方式理清逻辑

注意那些指针变化了，同时注意对前后节点的影响。

• 边界条件的处理

头节点，尾节点，空节点的特殊处理。

链表插入和删除的注意事项

• 特殊处理链表为空或长度为1

• 插入过程的调整

取得前后节点，将前节点的next指向新节点，新节点的next指向后节点。

• 删除过程的调整

取得前后节点，将前一个节点的next指针指向后一个节点。

• 头尾插入或删除

在逻辑的设计上应该考虑空节点的情况

链表翻转

• 特殊处理链表为空或长度为1

• 单链表的翻转

已翻转的头节点head，下一个节点now

1. 将now节点的next指向head
2. 将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个，则不调整。

1. 链表为空，长度<k或者k<2 直接返回

• 通过栈结构，实现逆序

1. 需要保留上次逆序的最后一位元素，修改其next。
2. 最后段不足k个，直接不修改。值将上次逆序的最后一个元素next设置好。
3. 第一组的第一个节点为头节点。

• 不使用栈结构，手动逆序

判断一个链表是否为回文结构

1. 将链表节点依次入栈，在弹出时与原链表依次比对。

2. 使用快行指针，通过二倍速的方式遍历。依次将慢指针的节点压入栈中，当快节点遍历到末尾时，慢指针正好处于中间位置。 继续移动慢指针，并与栈中弹出的元素做对比。(需要注意总量的奇偶)

   

3. 将后半部分链表进行逆序处理，从两端同时进行遍历比对

   

判断一个单链表是否有环，如有则返回入环节点。时间复杂度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)

首先都需要先去定单独的入环节点，然后

1. 是否入环之前已经相交

   

2. 是否入环时才相交，则入环位置节点相同

   

   如果相交点为loop1或者loop2，则为入环时才相交

3. 入环后才相交 循环其中一个环，若遇到另一个的入环节点则返回。

   

4. 否则，两链表并未相交

• #代码

/// 两个有环单链表是否相交
///
/// - 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  //并未相交
    }
}

复制代码

判断两个链表是否相交，并返回第一个相交的节点

1. 尝试找到各自的入环节点

2. 若一个有环一个无环，则不相交

3. 若都为无环，则按照上文《两个无环单链表是否相交》的方式查找

4. 若都为有环，则按照上文《判断两个有环单链表是否相交》的方式查找

• #代码

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)
    }
}

复制代码