第27~28天链表-北京尧图网络

一.链表反转让每个节点的next指向它的前一个节点。原1-2-3-NULL反转3-2-1-NULL1.初始化三个指针prev NULL; // 前驱指针指向当前节点的前一个currenthead; // 当前指针指向正在处理的节点nextNULL; // 后继指针保存当前节点的下一个2.循环处理每个节点循环条件current ! NULL //当前指向的不为空1.保存下一个节点next current-next //保存当前节点的下一个节点如果不保存修改 current-next 后后面的节点就丢失了next current-next; //保存节点2current-next prev; //1-NULLcurrent next; //继续处理节点22.反转指针方向current -nextprev; // 当前节点指向前一个节点这是反转的核心操作执行前prev-NULLcurrent-1-2-3-NULL执行后prev-NULL;current - 1 - NULL;↑ ( next指向了prev)现在节点1不再指向节点2而指向NULL3.移动前驱指针prev current; //prev移动到当前节点执行前:prev-NULL;current-1-NULL执行prev current:prev-1-NULLcurrent-1-NULL4.移动当前指针current next; //current 移到下一个节点执行前prev-1-NULLcurrent-1-NULLnext-2-3-NULL执行后prev-1-NULLcurrent-2-3-NULLnext -2-3-NULL3.返回新头指针return prev; // prev 指向原链表的最后一个节点新链表的头原链表最后一个节点 -prevcurrent-NULL返回prev,即新链表的头节点迭代法struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* current head; struct ListNode* next NULL; while (current ! NULL) { next current-next; // 1. 保存下一个 current-next prev; // 2. 反转指针 prev current; // 3. prev 前移 current next; // 4. current 前移 } return prev; }迭代法优点时间复杂度最优O(n)一次遍历完成空间复杂度最优O(1)只用了3个指针无栈溢出风险不递归不会爆栈代码简洁7行核心代码关键点必须保存next否则会丢失链表先反转再移动顺序不能错返回prev新链表的头节点时间复杂度时间O(n)空间O(1)二.头节点带头节点有一个额外的dummy 节点哨兵节点不存储实际数据不带头节点头指针直接指向第一个数据节点带头节点的优势优势说明统一操作插入删除不需要特判头节点空链表处理链表永远不会为空dummy 永远存在代码简洁减少分支判断逻辑统一更安全不会出现空指针异常三.链表插入1.尾插法带尾指针最常用90% 的场景使用尾插法创建链表保持顺序插入顺序链表顺序简单易用代码直观不易出错O(1) 高效带尾指针时插入操作是常数时间适用广泛从数组创建、从文件读取等都适用尾插法就是将新节点链接到当前链表的最后一个节点之后并更新尾指针指向新节点。list-tail-next newNode; //旧尾节点指向新节点list-tailnewNode; //更新尾指针2.头插法头插法就是将新节点插入到链表的第一个有效节点之前并更新头指针指向新节点。// 核心逻辑带dummy newNode-next dummy-next; // 新节点指向旧的头节点 dummy-next newNode; // dummy指向新节点 head newNode; // 更新head指针如果有维护head3.尾插法和头插法区别对比头插法尾插法插入位置链表头部第一个有效节点之前链表尾部最后一个节点之后时间复杂度O(1)O(1)维护tail 尾指针数据顺序逆序后插入的在前面保持顺序先插入的在前面核心操作newNode-next head;head newNode;tail-next newNode;tail newNode;是否需遍历不需要不需要维护tail指针适用场景栈LIFO、逆序构建队列FIFO、顺序构建缓存友好性较差访问分散较好顺序访问4.中间插入查找链表的中间节点使用快慢指针方法。快指针每次移动两步慢指针每次移动一步直到快指针到达链表末尾慢指针正好指向中间节点。创建新节点并将其插入到中间节点之后。更新新节点的next指向原中间节点的next然后将中间节点的next指向新节点。插入方式位置时间复杂度特点头插法链表头部O(1)插入顺序逆序尾插法链表尾部O(1)/O(n)保持顺序中间插入指定位置O(k)任意位置插入找到第 k-1 个节点前驱新节点指向原第 k 个节点前驱指向新节点。// 中间插入的核心操作 newNode-next prev-next; // ① 新节点指向原后继 prev-next newNode; // ② 前驱指向新节点四.节点查找1.中间查找快慢指针慢指针每次走一步快指针每次走两步。快指针到达末尾时慢指针在中间。如果有两个中间节点返回第二个2.查找倒数第k个节点快指针先走 k 步然后快慢指针一起走。快指针到达 NULL 时慢指针就在倒数第 k 个节点。五.删除删除第k个节点删除链表中第 k 个节点需要找到第 k 个节点的前驱然后进行删除操作。六.合并

第27~28天链表

相关推荐

Excel图片批量压缩4种方案对比与优化技巧

SolidWorks镜像实体与基准面：对称建模与斜面定位核心技巧

高压电源选型：基于失效模式的四维分类图谱

更多资讯

SpringBoot网络爬虫图书推荐系统设计与实现

SpringBoot 3.2作业管理系统：状态机驱动的教学工作流实现

SVPWM原理本质：三相电机控制的数学必然性

基于MediaPipe与CNN的摄像头手势控制鼠标实现详解

生物精炼模拟与技术经济分析：从流程模拟到LCA的集成方法

Actual Budget CLI 完全指南：用 @actual-app/cli 在终端管理与查询预算数据

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？