1 / 21
文档名称:

链表面试题精讲_七月算法出品.ppt

格式:ppt   大小:942KB   页数:21页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

链表面试题精讲_七月算法出品.ppt

上传人:xgs758698 2017/5/15 文件大小:942 KB

下载得到文件列表

链表面试题精讲_七月算法出品.ppt

相关文档

文档介绍

文档介绍:链表面试题精讲七月算法曹鹏 2015 年4月24日 2 /16 提纲?链表简介?面试题总体分析?一些例题?例1 链表的插入与(懒)删除?例2 链表翻转?例3单链表找环及起点和环长度?例4 两个链表找交点?例5复制带有随机指针的链表?例6 链表 partition 过程?总结链表简介?链表:一个元素和下一个元素靠指针连接(松散),不能 O(1) 直接访问到第 k个元素?单(向)链表:只能找到下一个节点?双(向)链表: 能找到上一个和下一个节点?循环(单、双)链表:首尾相接形成环? Java : LinkedList ? C++ : STL list ? C : 指针 3 /21 面试题总体分析?链表的基本操作?插入?删除?(分组)翻转?排序 Partition 、归并?复制?归并排序?找环、起点、长度?(倒数)第 k个节点?随机返回一个节点?和其他数据结构(二叉树)相互转换 4 /21 例1 链表的插入与删除?例1 在单链表里插入/删除一个节点?插入?哪些指针要修改?前驱的 next ,新节点的 next ?我们要找到插入之前的那个节点?特殊情况: 在 head 之前插入(包括 head == NULL) now->next = head; head = now; ?一般情况:在 pre 后面插入 now->next = pre->next; pre->next = now; 5 /21 例1 续1 ?删除?哪些指针要修改?前驱的 next ?我们要找到删除之前的那个节点?特殊情况? 删除 head temp = head->next; delete head; head = temp; ?一般情况,在 pre 后面删除 temp = pre->next; pre->next = temp->next; delete temp; 6 /21 例1 续2 ?思考题?双向链表的插入、删除?循环有序链表的插入、删除(建议断开、再连上) ?“懒”删除?要删除 now 这个节点 (不是最后一个) ?把now 复制成 now->next ? now->x = now->next->x ?删除 now->next 7 /21 例2 单链表翻转?例2 单链表翻转?思路: 把当前节点拿过来作为已经翻转结果的表头(堆栈类似) ListNode * result = 0; while (head) { temp = head->next; // 保存下一个节点 head->next = result; // 当前节点放到结果的开头 result = head; // 当前节点的头 head = temp; //head 指向下一个节点 } return result; 8 /21 例2 续?思考题?翻转部分链表 (Leetcode 92) ?如何找到第 m个元素和第 n个元素?如何处理前面和后面? ?保存前面部分最后一个元素?保存后面部分第一个元素?特殊情况? ?每k个元素翻转一次 (Leetcode 25) ?前面翻好的部分(小链表) ?要翻转的部分(K 个) ?后面没处理的部分(小链表) ?不足 k个怎么办 9 /21 例3 ?例3 单链表里是否有环?如果有起点是哪里? 环长度是多大? (最后一个节点 next 不是空,而是前面某个节点) (Leetcode 141, 142) ?方法 1 用一个 set 存放每个节点地址?注意: set 存放的元素必须“有序”,而地址都是“整数” set<ListNode * > have; for (; head; head = head->next) { if ((head) != ()) return true; (head); } return false; 10 /21

最近更新

商业街区夜间安全巡逻服务合同 3页

商务楼宇物业智能化升级改造合同 3页

商铺消防设施管理与物业管理合同 3页

园林景观景观石采购合同 3页

国有资产保荐人尽职调查与产权交易合同 2页

国际货物贸易磋商及合同履约监督服务合同 2页

国际贸易存货质押贷款服务协议 3页

国际贸易融资贷款合同书 3页

图书资料保管员聘用合同规范文本 3页

土地承包经营权租赁代理合同范本 3页

在线教育平台年度运营包年服务合同 3页

地下室小平方房屋租赁合同(含维修责任) 2页

地下室租赁市场调研与数据分析服务协议 3页

2025年最新助产士述职报告范文 6页

地契买卖风险评估与执行合同范本 3页

地磅租赁及称重设备租赁与租赁物处置合同 3页

2025年最新光棍节祝福句子 1光棍节经典祝福语.. 5页

2025年最新停水停电应急处理预案 21页

2025年最新保护环境倡议书七篇 10页

场地合作开发项目合作协议示范文本-@-1 3页

城乡综合规划与设计项目服务合同 3页

城市公交车辆安全运输服务协议 3页

城市公园草坪改造与景观设计施工合同 3页

城市地下综合管廊安装承包合同 3页

QC T 262-2024《汽车渗碳齿轮金相检验》 18页

桥梁建设协议书 5页

兰州市机动车停车场管理办法全文 11页

全国中学生物理竞赛实验指导书思考题参考答案.. 8页

教育教学基础知识填空题汇总 21页

DLT---电力建设施工质量验收及评价规程-第部分.. 37页