文档介绍：链表面试题精讲七月算法曹鹏 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