问题一：猫狗队列问题
问题二：矩阵旋转打印
思路：每次打印一个框，然后依次缩小
问题三：旋转正方形
思路：还是每次旋转一个框，和上一题思路一样
问题四：“之”字打印矩阵，要求额外空间复杂度为O(1)
思路：设计宏观结构，和上两题差不多
问题五：在行列排好序的矩阵（行有序列也有序）中找数，时间复杂度O(N+M)，从左下或者右上出发
问题六：打印两个有序链表的公共部分，类似外排merge
链表问题最优解来自空间复杂度，笔试越快愈好可以申请额外空间，面试的话要注重空间复杂度，聊的时候多聊好的方法
问题七：判断链表是否回文结构
简单方法：用一个栈得到逆序，依次比较，或者用双指针得到后半段的逆序（还是用栈）和前半段比较，这样笔试可以，但空间复杂度还是O(N)
面试方法：双指针找中点，然后后半段反向（记住最后还要把链表改回来），这样空间复杂度就是O(1)
问题八：链表的荷兰国旗问题
简单解法：用数组做，最后还原链表
进阶要求：实现稳定性，时间复杂度做到O(N)，额外空间复杂度O(1)，思路是用三个节点，遍历链表依次往后串，最后把三个链表串在一起
问题九：复制含有随机指针节点的链表
思路：先拷贝原有的next路线的链表，把每个节点和复制的节点塞到map中，利用map找复制链表的next和rand节点，这样空间复杂度是O(N)
改进方法：
/*重要*/问题十：两个链表相交问题，注意单链表
如何判断单链表是否有环：set，不用set就准备两个指针fast和slow，分别走两步和一步，如果有环fast和slow会相遇，此时fast回到head改成一次走一步，这样fast和slow会在起环处（loop）相遇，在找到是否有环后：
①两个链表都无环：链表1放到set，遍历链表2查有没有重复，不用set的话先遍历链表1找到最后节点和链表1长度，链表2也这样做，然后比较两个链表最后节点是否是一个，如果是一个说明中间会汇入一条链表（单链表），让较长的链表从长度差值处出发遍历两个链表，肯定能找到相遇点
②一个无环，一个有环：不可能相交
③两个都有环：三种拓扑
loop1==loop2：第二种结构
loop1！=loop2：第一或三种结构，如何区分：让loop1以next一直往下走，遇到loop2就是第三种，否则第一种
