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

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