当前位置： 首页 > article >正文

单链表的删除实战

article 2025/1/20 7:46:28

12.3 单链表的删除实战

12.3.1 流程图

  1. 不存在(除紧跟链表的第一个之外的，其他元素)也算删除成功！！！,但其实我们考虑的都是在链表中元素的删除！！！

​ 但是，如果前一个结点不存在，就可以甩锅，说明删除失败，是前一个点的原因！！！

​ 纠结的点！！！:(完全没必要)

​ 如果删除的是紧跟链表的第一个，会报错，因为此时不会return false(该位置前一个结点p是存在的),并且p->next值为 NULL,free(NULL)是无法进行编译的，所以出错。

​ 以上纯属个人钻牛角尖，其实单链表的删除，肯定是在链表中元素的删除，不会在已有结点之外。！！！

  1. 为什么这边一定要free()函数，因为删除呀，你肯定要释放空间呀，所以要free!!!

image-2023033111045907012.3.2 代码

#include <stdlib.h>
#include <stdio.h>

//定义结构体
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;

//尾插法新建链表
void LinkList_tail_insert(LinkList &L){
    L = (LinkList) malloc(sizeof (LNode));
    LinkList s, r = L;
    int x;
    scanf("%d", &x);
    while(x != 9999){
        s= (LinkList) malloc(sizeof (LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
}

//打印链表
void print_LinkList(LinkList L){
    L = L->next;
    while(L){
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

//找到指向第i个位置的指针
LinkList select_pos(LinkList L, int pos){
    int i = 0;//从第0个位置开始,且第0个位置是可以查的
    //判断所查位置的合理性
    if(pos < 0){
        return NULL;
    }
    while(L && i < pos){
        L = L->next;
        i++;
    }
    return L;
}

//删除链表
bool LinkList_Delete(LinkList &L, int pos){
    LinkList p = select_pos(L, pos-1);
    if(NULL == p){
        return false;
    }
    LinkList q = p->next;
    p->next = q->next;
    free(q);//重要！！！
    return true;
};

int main() {
    LinkList L;
    LinkList_tail_insert(L);
    print_LinkList(L);
    bool res;
    res = LinkList_Delete(L, 5);
    if(res){
        printf("success\n");
        print_LinkList(L);
    }else{
        printf("failure\n");
        print_LinkList(L);
    }
    return 0;
}

12.4 2019年41题–题目解读与解题设计

12.4.1 题目简介

image-20230331143537682

12.4.2 题目解读

  1. 空间复杂度为O(1)，即我们不能申请额外的空间(如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1))。如下图所示

image-20230331144431719

  1. 解题步骤：
  1. 找到链表的中间结点
  2. 前面一半为链表L(即原来的头结点),后面一半为链表L2(新的头结点)；
  3. 将链表L2进行原地逆置
  4. 将L与L2合并

12.4.3 解题设计

12.4.3.1 如何找到链表的中间结点？

定义俩个指针p_front和p_back

  1. p_front 在前面，每次先走俩步
  2. p_back 在后面，每次再走一步
  3. 直到p_front值为NULL，p_front不走了，p_back也不走了

(1)当n为奇数时：

image-20230331145636871

Fig 1.第一次移动

image-20230331145703290

Fig 2.第二次移动

Fig 3. 第三次移动

image-20230331150153650

Fig 4.第四次移动(最后一次)

(2)当n为偶数时：

image-20230331151311200

Fig 1.第一次移动

image-20230331151333769

Fig 2.第二次移动

image-20230331151458739

Fig 3.第三次移动

==！！！==一般默认第一个链表放元素多的元素，所以此时L：{a1、a2、a3}；L2：{a4、a5、a6};

综上：如上述操作完毕后，头结点保持不动，新建头结点L2指向p_back的后一个结点即可。

12.4.3.2 如何将L2逆置？

  1. 流程图

image-20230331153904425

  1. 示意图

image-20230331154114706

Fig 1.初始状态

初始状态a1->a2->a3->a4->a5->a6->NULL

第一次移动之前：a1<-a2，a3->a4->a5->a6->NULL

image-20230331154128399

Fig 2.第一次移动

此时a1<-a2<-a3，a4->a5->a6->NULL

image-20230331154138606

Fig 3.第二次移动

此时a1<-a2<-a3<-a4，a5->a6->NULL

image-20230331154148771

Fig 4.第三次移动

此时a1<-a2<-a3<-a4<-a5，a6->NULL

image-20230331154204250

Fig 5.此次没有成功

此次由于t已经变成NULL了，此时r指向倒数第二个元素，s指向倒数第一个元素，再进行一次s->next=r

此时a1<-a2<-a3<-a4<-a5<-a6,但由于默认最后一个结点的指针域为NULL，所以L2->next->next=NULL

此时NULL<-a1<-a2<-a3<-a4<-a5<-a6,并且重新赋值头指针，将新的第一个元素赋值给头指针L2->s

12.4.3.3 将L和L2链表合并，合并时轮流放入一个结点

  1. 流程图

image-20230402220205830

Fig 1.总体流程图

image-20230402220217617

Fig 2.循环流程图

2.动态示意图

image-20230402220232534

Fig 1.初始状态(进入循环之前)

首先：pcur=L->next;p=p->next;q=q->next;

指针作用
pcur指示当前链表最后一个元素
p指向链表L中将要被合并的元素
q指向链表L2中将要被合并的元素

此时因为L中第一个元素不动，所以p=p->next

image-20230402220243474

Fig 2.第一次循环之后状态

pcur->next=q;

q=q->next;

pcur=pcur->next;

pcur->next=p;

p=p->next;

pcur=pcur->next;

image-20230402220257654

Fig 3.第二次循环之后状态

循环代码见上图；

但是此时的p指针指向了NULL，所以下一次并不进入循环，而是直接将q指针所指的元素，接在pcur的后面。

12.5 真题题目代码实战

注意点!!!

  1. L2需要分配头结点；
  2. 在找到中间结点的子函数中，要注意p_front指针的合理性，区别于n为奇数和偶数的情况！！！，且空指针的next不存在；
  3. 注意修改新旧链表的头部与尾部；
  4. 逆置的时候，考虑L2没有结点和只有一个结点的特例；
  5. 合并时，p从第二个结点开始，因为第一个结点固定了；
#include <stdio.h>
#include <stdlib.h>

//定义结构体
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;

//头插法新建链表
void LinkList_head_insert(LinkList &L){
    L = (LinkList) malloc(sizeof (LNode));
    L->next = NULL;
    LinkList s;
    int x;
    scanf("%d", &x);
    while(x != 9999){
        s =  (LinkList) malloc(sizeof (LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
}

//打印链表
void print_LinkList(LinkList L){
    L = L->next;
    while(L){
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

//找到中间结点，并且使头结点L2指向中间结点以后的链表,并且修改L
void find_middle(LinkList &L, LinkList &L2){
    L2 = (LinkList) malloc(sizeof (LNode));//给L2的头结点分配空间
    LinkList p_front, p_back;
    p_front = L->next;
    p_back = L->next;
    while(p_front){
        p_front = p_front->next;
        //NULL是没有next的值的，系统会报错，所以我们提前退出程序(当n为奇数的退出条件)
        if(!p_front){
            break;
        }
        p_front = p_front->next;
        //为了保证n为偶数个时的均匀分配(当n为偶数的退出条件)
        if(!p_front){
            break;
        }
        p_back = p_back->next;
    }
    L2->next = p_back->next;
    p_back->next = NULL;
}

//逆置L2
void reverse_LinkList(LinkList &L2){
    LinkList r,s,t;
    r = L2->next;
    //如果没有结点，直接返回，不需要操作
    if(!r){
        return;
    }
    //如果为一个结点，直接返回，不需要操作
    s = r->next;
    if(!s){
        return;
    }
    t = s->next;
    while(t){
        s->next = r;
        r = s;
        s = t;
        t = t->next;
    }
    //最后的倒数第一和倒数第二的元素
    s->next = r;
    //逆置之后的最后一个元素的指针域赋值为NULL
    L2->next->next = NULL;
    //逆置之后，要把头结点连接上新的第一个元素
    L2->next = s;
}

//将L与新L2合并
void merge_LinkList(LinkList &L, LinkList &L2){
    LinkList pcur, p, q;
    //pcur指示合并链表的最后一个结点
    pcur = L->next;
    //q指示L2链表的准备进入的结点
    q = L2->next;
    //p指示L链表的准备进入的结点
    p = L->next;
    //因为L中第一个结点不动，所以p应该指向L2的第二个结点
    p = p->next;
    while(p && q){
        //因为第一个元素为L的第一个元素，所以先存q，再存p
        pcur->next = q;//pcur指向q
        pcur = pcur->next;//pcur向后移
        q = q->next;//q向后移
        pcur->next = p;//与q同理
        pcur = pcur->next;
        p = p->next;
    }
    //L可能还剩下一个，加上去
    if(p){
        pcur->next = p;
    }
    //L2可能还剩下一个，加上去
    if(q){
        pcur->next = q;
    }
}

int main() {
    LinkList L, L2;
    LinkList_head_insert(L);
    print_LinkList(L);
    printf("--------------------------\n");
    find_middle(L, L2);
    print_LinkList(L);
    print_LinkList(L2);
    printf("--------------------------\n");
    reverse_LinkList(L2);
    print_LinkList(L);
    print_LinkList(L2);
    printf("--------------------------\n");
    merge_LinkList(L,L2);
    print_LinkList(L);
    return 0;
}

12.6 分析真题代码的时间复杂度

  1. find_middle()函数，循环的次数为n/2，所以时间复杂度为O(n);
  2. reverse_LinkList()函数，只遍历了L2链表，遍历长度为n/2，所以时间复杂度为O(n);
  3. merge_LinkList()函数，循环遍历次数也为n/2，所以时间复杂度为O(n);

http://www.kler.cn/a/510393.html

相关文章：

  • Visual Studio Code + Stm32 （IAR）
  • vue集成高德地图API实现坐标拾取功能
  • [JavaScript] 深入理解流程控制结构
  • 如何学习网络安全？有哪些小窍门？
  • C++ 强化记忆
  • Redis系列之底层数据结构字典Dict
  • NEC纪实 ：2024全国机器人大赛 Robocon 常州工学院团队首战国三
  • QT笔记- Qt6.8.1 Android编程 添加AndroidManifest.xml文件以支持修改权限
  • VB.net实战(VSTO)：解决WPS Ribbon图标灰色背景
  • 简单日志宏实现（C++）
  • Invicti-Professional-V25.1
  • MATLAB基础应用精讲-【数模应用】基于粒子群算法的风光储微电网经济运行优化调度（附MATLAB代码实现）
  • 《自动驾驶与机器人中的SLAM技术》ch8：基于预积分和图优化的紧耦合 LIO 系统
  • Qt Desiogn生成的ui文件转化为h文件
  • kubernetes简介
  • LLM - 大模型 ScallingLaws 的 CLM 和 MLM 中不同系数(PLM) 教程(2)
  • 图论DFS：黑红树
  • Python库之PyAutoGUI安装以及使用方法
  • 使用 Hadoop 实现大数据的高效存储与查询
  • 题海拾贝：力扣 反转链表
  • Source insight快捷导入工程流程 Source insight导入MDK工程文件
  • C# 委托和事件(Lambda表达式)
  • STL--list（双向链表）
  • Mousetrap：打造高效键盘快捷键体验的JavaScript库
  • PageHelper快速使用
  • 令牌主动失效机制实现——Redis登录优化