单链表的建立（尾插法与头插法）

文章目录尾插法带头结点代码代码解读不带头结点代码时间复杂度O(n)头插法带头结点应用不带头结点时间复杂度O(n)尾插法核心思路始终维护一个尾指针r永远指向链表最后一个结点新结点直接接在r的后面然后rs更新尾部。带头结点代码// 带头结点// 正向建立单链表LinkListList_TailInsert(LinkListL){intx;// 设 ElemType 为 intL(LinkList)malloc(sizeof(LNode));// 建立头结点初始化空表LNode*s,*rL;// r 为表尾指针scanf(%d,x);// 输入结点的值while(x!9999){// 输入 9999 表示结束// 在 r 结点之后插入元素 xs(LNode*)malloc(sizeof(LNode));s-datax;r-nexts;rs;// r 指向新的表尾指针永远保持 r 指向最后一个结点scanf(%d,x);}r-nextNULL;// 尾结点指针置为 NULLreturnL;}代码解读// 定义typedefstructLNode{...}LNode,*LinkList;// ↑ 没有 ↑ 有*L(LinkList)malloc(sizeof(LNode));// 建立头结点初始化空表s(LNode*)malloc(sizeof(LNode));这里强制转换类型是一致的。LinkList无*号是因为声明是就有而LNode声明是没有。LinkList 强调是一个链表LNode强调是一个结点。其都能代表是指向头指针。不带头结点代码// 不带头结点 尾插法正向建立单链表LinkListList_TailInsert(LinkListL){intx;LNULL;// 1.初始化为空表不带头结点L直接指向第一个数据结点LNode*s,*rNULL;// r 为表尾指针初始为 NULLscanf(%d,x);// 输入结点的值while(x!9999){// 输入 9999 表示结束s(LNode*)malloc(sizeof(LNode));if(sNULL){// 内存分配失败处理returnL;// 如果已建部分节点返回当前链表}s-datax;// 注意s-next 暂不置空最后统一封尾// 2.【核心区别】判断是不是第一个结点if(LNULL){// 第一个结点直接让头指针 L 指向它Ls;rs;}else{// 后续结点挂在尾指针 r 后面r-nexts;rs;}scanf(%d,x);}// 3. 封尾如果表不为空将最后一个结点的 next 置 NULLif(r!NULL){r-nextNULL;}returnL;// 返回头指针虽然引用已修改了外部L但保留返回以支持链式调用}时间复杂度O(n)头插法核心原理新结点永远插入在头结点后面带头结点// 逆向建立单链表带头结点 头插法LinkListList_HeadInsert(LinkListL){LNode*s;intx;L(LinkList)malloc(sizeof(LNode));// 创建头结点// 只要是初始化单链表都先把头指针指向 NULLL-nextNULL;// 初始为空链表以防有脏数据scanf(%d,x);// 输入结点的值while(x!9999){// 输入9999循环结束s(LNode*)malloc(sizeof(LNode));// 创建新结点s-datax;s-nextL-next;L-nexts;// 将新结点插入表中L 为头指针scanf(%d,x);}returnL;}应用最终链表顺序与输入顺序相反所以又叫逆向建表。不带头结点// 不带头结点 头插法建立单链表LinkListList_HeadInsert(LinkListL){LNode*s;intx;LNULL;// 不带头结点初始空链表scanf(%d,x);while(x!9999){s(LNode*)malloc(sizeof(LNode));if(sNULL)returnL;// 分配失败直接返回s-datax;s-nextL;Ls;// 更新头指针新结点作为第一个结点scanf(%d,x);}returnL;}时间复杂度O(n)