1.用数组结构实现大小固定的队列和栈
一面一题，相对简单。
栈：设置一个index，用数组的大小size来限制，每次push()、pop()操作index位置的值
队列：设置一个start和end，用size来约束，每次poll()时操作start位置的数，start++；每次offer()时操作end位置的数,end++，start和end可以循环
2.实现一个特殊的栈，在现实栈的基本功能的基础上，再实现返回栈中最小元素的操作。
要求：(1)pop、push、getMin操作的时间复杂度都是O(1);(2)设计的栈类型可以使用现成的栈结构
设计两个栈。pop、push都用data实现。getMin用min栈实现，同时弹出，同时压栈
3.如何仅用队列结构实现栈结构？如果仅用栈结构实现队列结构？
如何用队列结构实现图的深度优先遍历？
（1）用两个队列实现一个栈。设置一个队列为data，一个队列为help。从data里面复制数据到help里面要留一个数据
（2）用两个栈实现一个队列。设置一个栈为push，一个栈为pop。两个限制：从push到pop的数要一次倒完；pop里面有数据则一定不要从push里面倒数据
4.之字形打印矩阵
和螺旋打印矩阵一样宏观思路（以后相似的打印问题可以用宏观的思路）。。先设置A，B同时在左上角，每次AB同时移动，A向右移动，B向下移动，B移到最底再向右移动，A移到最右再向下移动，每次打印AB对角线上的元素。准备一个布尔变量用来设置每次是从A打印到B还是从B打印到A.
5.将单向链表按某值划分为左边小，中间相等右边大的形式
初阶思路：荷兰国旗问题，不能保证稳定性。用一个数组储存所有的元素，对数组进行划分。然后再建立一个单链表，依次将这些值串起来。
进阶思路：要求保证稳定性，则遍历一遍链表，建立三个链表，按链表中的顺序依次将小于num的值串起来，等于num的值串起来，大于num的值串起来，再总体串起来。6个变量搞定。
6.对一个带有随机指针的链表进行深拷贝
解法一：使用哈希表。额外空间复杂度为O（N）.
解法二（进阶）：不使用哈希表。将每个被复制的节点放在原节点的后面。
7.两个单链表相交的一系列问题
这是三个面试问题的集合：（1）判断一个单链表是否有环（2）找到两个无环单链表的第一个相交节点（3）两个单链表的第一个相交的节点
（1）判断是否有环：第一个方法，用HashSet,依次放入节点;第二个方法，准备快慢指针，如果有环，则快指针一定会和慢指针在环上相遇。在相遇点将fast指针重置为第一个节点，然后fast和slow依次向后移动一个点，再次相遇的节点即为环的入口节点（2）HashSet；Y形的相交形式，可以将长度较长的链表的头节点先向前移动（len1-len2）个位置，然后再同时向后移动，相等的节点即为第一个相交节点（3）一个链表有环一个链表无环，则两个链表一定不会相交。则变为两个有环链表的相交节点。两个有环链表的拓扑关系一共有三种：（1）各不相交（2）重复节点的一部分构成一个环loop1=loop2（3）重复节点的所有部分构成一个环loop1 != loop2。head为头节点，loop为环的入口
主逻辑：
京公网安备 11010502036488号