文章目录带头结点的删除按位序删除代码时间复杂度指定结点的删除代码时间复杂度O(1)带头结点的删除按位序删除删除表 L 中的第 i 个位置的元素并用 e 返回删除元素的值。找到第 i-1 个结点将其指针指向第 i1 个结点并释放第 i 个结点代码#includestdio.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;// 带头结点单链表 按位删除第i个元素boolListDelete(LinkListL,inti,inte){if(i1)// 位序从 1 开始小于 1 直接非法returnfalse;LNode*p;// 指针 p 指向当前扫描到的结点intj0;// 当前 p 指向的是第几个结点pL;// L指向头结点头结点是第 0 个结点不存数据// 寻找第 i-1 个前驱结点while(p!NULLji-1){// 循环终止条件走到第 i-1 号结点或者链表走完pNULLpp-next;j;}if(pNULL)// 1. i太大找不到i-1结点returnfalse;if(p-nextNULL)// 2. i-1后面没有结点不存在第i个结点returnfalse;LNode*qp-next;// q指向待删除的第i个结点eq-data;// 将被删元素存入e带回p-nextq-next;// 把待删结点从链表断开free(q);// 释放内存防止内存泄漏returntrue;}// 配套初始化boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));if(LNULL)returnfalse;L-nextNULL;returntrue;}时间复杂度最好时间复杂度O(1)最坏、平均时间复杂度O(n指定结点的删除指定结点时最后一个结点时需要特殊处理。代码// 删除单链表中p所指向的结点无法删除最后一个结点boolDeleteNode(LNode*p){if(pNULL)returnfalse;// p是最后一个结点此方法失效if(p-nextNULL)returnfalse;LNode*qp-next;// q指向p的后继结点p-dataq-data;// 把后继结点的数据复制到p结点// 或p-data p-next-data;p-nextq-next;// p跳过q断开后继结点可能是一个结点也可能是一个NULLfree(q);// 释放q结点内存returntrue;}时间复杂度O(1)如果p是最后一个结点只能从表头开始依次寻找p的前驱时间复杂度为O(n)。
文章目录带头结点的删除按位序删除代码时间复杂度指定结点的删除代码时间复杂度O(1)带头结点的删除按位序删除删除表 L 中的第 i 个位置的元素并用 e 返回删除元素的值。找到第 i-1 个结点将其指针指向第 i1 个结点并释放第 i 个结点代码#includestdio.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;// 带头结点单链表 按位删除第i个元素boolListDelete(LinkListL,inti,inte){if(i1)// 位序从 1 开始小于 1 直接非法returnfalse;LNode*p;// 指针 p 指向当前扫描到的结点intj0;// 当前 p 指向的是第几个结点pL;// L指向头结点头结点是第 0 个结点不存数据// 寻找第 i-1 个前驱结点while(p!NULLji-1){// 循环终止条件走到第 i-1 号结点或者链表走完pNULLpp-next;j;}if(pNULL)// 1. i太大找不到i-1结点returnfalse;if(p-nextNULL)// 2. i-1后面没有结点不存在第i个结点returnfalse;LNode*qp-next;// q指向待删除的第i个结点eq-data;// 将被删元素存入e带回p-nextq-next;// 把待删结点从链表断开free(q);// 释放内存防止内存泄漏returntrue;}// 配套初始化boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));if(LNULL)returnfalse;L-nextNULL;returntrue;}时间复杂度最好时间复杂度O(1)最坏、平均时间复杂度O(n指定结点的删除指定结点时最后一个结点时需要特殊处理。代码// 删除单链表中p所指向的结点无法删除最后一个结点boolDeleteNode(LNode*p){if(pNULL)returnfalse;// p是最后一个结点此方法失效if(p-nextNULL)returnfalse;LNode*qp-next;// q指向p的后继结点p-dataq-data;// 把后继结点的数据复制到p结点// 或p-data p-next-data;p-nextq-next;// p跳过q断开后继结点可能是一个结点也可能是一个NULLfree(q);// 释放q结点内存returntrue;}时间复杂度O(1)如果p是最后一个结点只能从表头开始依次寻找p的前驱时间复杂度为O(n)。
