#牛客堂直播视频#常见面试题精讲（五）（8.19）
【本期题目】
1、两个单链表相交的一系列问题
单链表可能有环,也可能无环。给定两个单链表的头节点 head1 和 head2, 这两个链表可能相交,也可能不相交。
请实现一个函数,如果两个链表相交,请返回相交 的第一个节点;如果不相交,返回 null 即可。
要求:如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。
2、设计有setAll功能的哈希表
哈希表常见的三个操作是 put、get 和 containsKey,而且这三个操作的时间复杂度为 O(1)。现在想加一个 setAll 功能,就是把所有记录的 value 都设成统一的值。请设计并实现 这种有 setAll 功能的哈希表,并且 put、get、containsKey 和 setAll 四个操作的时间复杂度 都为 O(1)。
3、设计 RandomPool结构
设计一种结构,在该结构中有如下三个功能:
1，insert(key):将某个key加入到该结构,做到不重复加入。
2，delete(key):将原本在结构中的某个key移除。
3，getRandom():等概率随机返回结构中的任何一个key。
要求：Insert、delete 和 getRandom 方法的时间复杂度都是 O(1)。
4、一种消息接收并打印的结构设计
消息流吐出 2,一种结构接收而不打印 2,因为 1 还没出现。
消息流吐出 1,一种结构接收 1,并且打印:1,2。
消息流吐出 4,一种结构接收而不打印 4,因为 3 还没出现。
消息流吐出 5,一种结构接收而不打印 5,因为 3 还没出现。
消息流吐出 7,一种结构接收而不打印 7,因为 3 还没出现。
消息流吐出 3,一种结构接收 3,并且打印:3,4,5。
消息流吐出 9,一种结构接收而不打印 9,因为 6 还没出现。
消息流吐出 8,一种结构接收而不打印 8,因为 6 还没出现。
消息流吐出 6,一种结构接收 6,并且打印:6,7,8,9。
已知一个消息流会不断地吐出整数1~N，但不一定按照顺序吐出。如果上次打印的数为i，那么当i+1出现时,请打印i+1及其之后接收过的并且连续的所有数,直到1~N全部接收并打印完，请设计这种接收并打印的结构。
注：下面回帖给出了源代码供参考。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者，电子工业出版社7月底将出版发行，书籍涉及算法与数据结构编程题目240道以上，并且个人实现出最优解，大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30，直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客3群260877110
【本期答案领取地址】
加入牛客讨论5群（272820159）
群资料中文件：＃牛客堂直播视频＃2015.8.19
