单链表的按位序插入（带头结点与不带头结点）

文章目录带头结点 的 按位序插入代码核心代码解读寻找 i-1 结点判断 i 越界新建结点并连接指针不带头结点 的 按位序插入代码不带头结点单链表特征代码解读i 1 表头插入分支i ≥ 2寻找前驱结点以及连接结点时间复杂度不同点带头结点与不带头结点的插入代码直观对照带头结点没有 i1 分支不带头结点先单独处理 i1带头结点 的 按位序插入代码#includestdio.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;// 在第 i 个位序插入元素 e 带头结点单链表boolListInsert(LinkListL,inti,inte){// 1. 位序不能小于 1if(i1)returnfalse;LNode*p;// 遍历指针用来寻找第 i-1 个结点intj0;// 记录 p 当前是第几个结点,即当前指向的位序头结点是第 0 位pL;// p 初始指向头结点头结点定义为第 0 位无数据// 循环找到第 i-1 个前驱结点while(p!NULLji-1){pp-next;j;}// p为空说明 i 超过链表长度 1位置非法if(pNULL)returnfalse;// 新建结点 sLNode*s(LNode*)malloc(sizeof(LNode));s-datae;// 先让 s 接上 p 后面的结点再修改p的后继s-nextp-next;p-nexts;returntrue;}// 配套初始化函数带头结点boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));if(LNULL)returnfalse;L-nextNULL;returntrue;}intmain(){LinkList L;InitList(L);// 在第1位插入10、第2位插入20ListInsert(L,1,10);ListInsert(L,2,20);return0;}核心代码解读寻找 i-1 结点LNode*p;intj0;// j 记录当前 p 对应的位序pL;// p 一开始指向头结点规定头结点是第 0 位while(p!NULLji-1){// i-1即循环次数pp-next;j;}核心规则插入第i个位置必须先找到第 i-1 个结点前驱循环两个条件缺一不可p ! NULL防止p-next访问空指针崩溃j i - 1没走到前驱结点就继续后移。两种退出循环情况j i-1成功找到前驱正常插入p NULL链表遍历完仍没走到i-1i过大位置不存在。判断 i 越界if(pNULL)returnfalse;// 例如链表现有 2 个元素最大可插入 i3传入 i4循环结束 pNULL插入失败。新建结点并连接指针LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;指针顺序绝对不能颠倒先让新结点s接上p原来后面的结点保存后半段链表再让p指向新结点s错误写法断链丢失后面所有节点p-next s;s-next p-next; // p-next已经变成s自循环不带头结点 的 按位序插入代码#includestdio.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;// 不带头结点 初始化L直接置NULL不malloc不创建任何结点// LNULL 代表链表为空boolInitList(LinkListL){LNULL;returntrue;}// 在第 i 个位序插入元素 e 【不带头结点单链表】boolListInsert(LinkListL,inti,inte){if(i1)// 位序从 1 开始0 和负数非法returnfalse;// 情况1插入第1个位置表头需要修改头指针L单独处理if(i1){LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextL;Ls;// 头指针指向新结点returntrue;}// 情况2i≥2寻找第 i-1 个结点LNode*p;intj1;// p一开始指向第1个数据结点pL;// L直接指向第一个有效结点无头部空结点while(p!NULLji-1){pp-next;j;}if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;returntrue;}intmain(){LinkList L;InitList(L);// 不带头结点初始化 LNULLListInsert(L,1,10);// 第1位插入ListInsert(L,2,20);// 第2位插入return0;}不带头结点单链表特征LinkList L直接指向第一个有效数据结点空链表判定L NULL表头插入i1特殊需要修改头指针L必须单独分支带头结点链表不需要单独处理表头这是两者最大区别。代码解读i 1 表头插入分支LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextL;Ls;执行顺序新建结点s存入数据es-next L新结点接上原来链表第一个结点L s头指针更新让L指向新结点新的表头。i ≥ 2寻找前驱结点以及连接结点目标插入第 i 个位置要先找到第 i-1 号结点。后续逻辑和带头结点一样LNode*p;intj1;// p一开始指向第1个数据结点pL;// L直接指向第一个有效结点无头部空结点while(p!NULLji-1){// 循环找到第 i-1 个结点pp-next;j;}if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextp-next;//先让 s 接住 p 后面的链表再修改 p 的后继。p-nexts;时间复杂度最好时间复杂度O(1)最坏时间复杂度O(n)平均时间复杂度O(n)不同点带头结点与不带头结点的插入不同点对比带头结点不带头结点初始化malloc创建头结点L永远不为NULLL NULL不创建任何结点空表即没有结点空链表判断L-next NULLL NULLi1表头插入无需单独分支统一代码前驱就是头结点必须单独if(i1)分支需要修改头指针L遍历指针初始设置p Lp一开始指向头结点j 0头结点编号0p Lp一开始指向第1个数据结点j 1第一个有效结点编号1前驱查找逻辑所有i统一处理无特殊情况i1特殊处理i≥2才走循环寻找前驱代码直观对照带头结点没有 i1 分支pL;intj0;while(p!NULLji-1){pp-next;j;}不带头结点先单独处理 i1if(i1){// 表头插入单独逻辑s-nextL;Ls;returntrue;}// i≥2才执行下面遍历pL;intj1;while(p!NULLji-1){pp-next;j;}