#学习笔记
第1周-第3课 | 数组、链表、跳表
###1. 数组、链表、跳表的基本实现和特性
####Array
- 数组常见写法
- Java、C++: int a[100];
- Python: list = []
- JavaaScript: let x = [1,2,3]
- 在语言上有一个标准的叫法叫做泛型，也就是说任何一个单元类型也都可以放进去。
- 底层的硬件实现有一个叫做内存管理器的东西，每当申请数组，计算机实际上是在内存中开辟了一段连续的地址，每一个地址就直接可以通过内存管理器进行访问。
- 直接访问第一个元素和访问中间的任何一个元素时间复杂度都是一样的，也就是常数时间称为O(1)。
- 它可以随机的访问任何的一个元素，所以它的访问时间非常快，这就是它的特性之一。
- 数组问题：关键在于要增加删除数组元素的时候会进行一些相应的操作。
- 插入元素操作会导致不再是常数级的了，而是O(n)的时间复杂度。
- 在最坏的情况下，需要挪动整个数组。在好的情况下，插入最后面的话就变成O(1)了。平均来说，它平均要移一半的元素位置，然后将元素插入进去。
- 删除元素的操作，先将要删除的元素清除，然后把后面元素往前挪动，然后把最后一个元素设置为空，能够唤起比如Java的垃圾回收机制、或者是必须手动管理内存，就把这个数组的size减少。
- Java 的 ArrayList 如果当前长度不够的话会直接，那么就直接new一个新的数组出来，新的数组长度为当前长度再乘以2，然后把老数组的值拷贝到新的数组去，返回新的数组即可。
- 由此可见，如果对Java中的ArrayList做大量修改的话，它会涉及到非常多少的array copy，这样它的时间复杂度其实是偏低的或者相对来说不是特别高效的。
Linked List
- 链表这个数组结构就是为了弥补数组的缺点
- 在一些修改和添加操作、删除操作比较频繁的情况下，数组这个时候其实并不好用。
- 链表所做的一件事情就是元素定义好之后，它有所谓的value和next，netx指向下一个元素，那么串在一起就变成了一个类似于数组的这么一个结构。
- 它的每一个元素，一般用Class来定义。和数组不太一样，一般来说都要定义一个Class，这个Class一般叫node就行，里面有两个成员变量，一个成员变量是value，这个成员变量也可以是一个类，另外有一个next指针，指向它的下一个元素，那么在Java的话就是next，它是一个引用到下一个元素去，串在一起就变成了一个链表。
- 如果只有一个next指针的话，叫做单链表。
- 有时候需要往前面指一个，就叫做它的先前指针叫做prev 或者 previous，那么这个链表就叫做双向链表，既能往前面走，又能往后面走。它的头指针一般用head表示，它的尾指针用tail来表示，最后一个元素它的next指针指向空。为什么？因为没有next指针了。
- 另外一种情况，如果尾指针的next也可以指回到头指针来，这个就叫做循环链表。也就是说把头指针指向前面，这就变成一个循环链表了。类似一条蜈蚣它的头和尾连在一起。
- Linked List的定义: Linked List Class本身当成一个大的class定义在外面，而里面的node也是写成一个class，里面有它的属性值，next指针指向下一个它的构造函数。
- CMU 15121计算机基础课程
- Java代码里面，LinkedList它不在是一个单链表，而是一个双向链表，Java里面的LinkedList它是一个很标准的双向链表结构。
- 链表的增加和删除操作以及它的时间复杂度为多少。
- 增加节点
- 首先为新元素创建一个节点NewNode，然后将它放到链表中去，前面的next指向NewNodel的节点，NewNode的next指针指回去即可。就是把它的前继节点的next指针指向新节点，新节点next指针指向之前的下一个节点即可。
- 这里的增加操作总共要操作两次，但是是常数次的，所以它是O(1)的操作。
- 删除节点
- 是增加节点的逆操作，将要删除的结点称为Target Node，把它的前驱结点的next打掉移到后继的结点去，前驱结点的next直接指向下一个节点。
- 从这两个操作可以发现，它不设计到如果增加删除任何节点，它没有引起整个链表的群移操作，也不需要复制元素，正是因为这样，所以它的移动的效率和修改的效率非常高为O(1)。
- 但是也是因为这么一个结构，导致了你访问了这个链表中任何一个位置，它的操作就不再是简单了。
Double Linked List
访问的话，如果在任意位置，假设平均数是在中间位置，那么必须从头结点一步一步往后挪，直到挪到中间节点，这样它的操作是线性的n的，也就是O(n)的算法。
Linked List时间复杂度表
操作 | 复杂度
— | —
prepend | O(1)
append | O(1)
lookup | O(n)
insert | O(1)
delete | O(1)
- lookup需要随机访问里面任何一个元素的话，它的时间复杂度的平均值是O(n)的，这也就是链表它的问题所在。
- 并没有所谓的完美的一种数据结构。
- Array的时间复杂度
操作 | 复杂度— | —
prepend | O(1)
append | O(1)
lookup | O(1)
insert | O(n)
delete | O(n)Skip List 跳表
- 跳表主要在工程中主要在Redis里面进行运用，但是这个数据结构并没有在面试的时候出题，让大家写程序，所以的话以理解它的工作原理为主。
- 跳表是为了优化或者是补足链表的缺陷而设计出来的。
- 链表的缺陷就是它的look up 的时间为O(n)的。为什么为O(n)，究其本质，它是一个简单的线性结构，一维的结构，所以要访问某个元素位置的话，必须从起始位置1开始，每次往后挪一步，一直到挪到某个元素位置，就取出这个元素里面的内容。
- 如何给链表加速
- 进行加速的一个中心思想，记下来，后面的话不断地过遍数，还会回到这样的一个中心思想来，而这个思想其实贯穿于整个所谓的算法数据结构，也贯穿于整个所谓的数学和无力世界里面进行分析。
- 链表的优化的思想其实就是所谓的1.升维，或者叫2.空间换时间。
- 问题的本质：如果要随机访问的话，如果对于简单的原始链表一维结构的话，假设要访问7，就只能一步一步往后挪，挪到7，所以它的时间复杂度毫无疑问还是O(n)的。
- 简单的优化就是增加头指针的同时，再加一个尾指针，这时发现，如果指针加一个尾指针也不够，它必须从最后往前一步一步地挪，也需要挪O(n)的次数。
- 再次优化思路：就是升维，所谓升维的话就是不在是一维结构，将它变为二维结构。其实就是和增加一个尾指针一样，多增加几个指针而已。
- 不仅仅增加一个头指针和尾指针，可以再增加一个所谓的中指针，那放到中间之后，当访问中间的元素就变成O(1)了。当然也可以插更多的指针。比如中间的中间的位置，这样发现速度好像是提起来了。
- 添加第一级索引：它的头指针指向头指针，它的下一个位置就指向next+1的位置，也就是索引基于链表，链表走向next，这里每次走向next+1，也就是两倍的next。可以认为next每次速度是1，而一级索引每次速度是2，它走起来就会更快。
- 可以再增加一级索引，在第一级索引的基础上再乘以二，就每次跨四个元素，这样跨过来之后，走到某个位置可能只需要一步。
- 如何提高链表线性查找的效率？
- 以此类推，增加多级索引。
- 注意，这里它的时间复杂度也没有降到O(1)，而是降到
- 跳表时间复杂度分析
- 跳表的维度不再是一维，它其实是变成一个二维空间了，如果升成三维按道理应该更快。同理用了更多的节点，所以它的空间的消耗会比一维更大，所以这里叫做空间换时间的一种策略。
- 跳表查询到的时间复杂度是O(logn)的复杂度来进行查询。
- 索引的高度是O(logn)，在跳表中查询任意数据的时间复杂度就是O(logn)。
- 也就是从最朴素的原始链表它的O(n)的时间复杂度，降到了O(log2n)的时间复杂度，这是一个很大的改进。
- 现实中的，我们在用跳表的情况下，它会由于这个元素的增加和删除，导致它的索引不断更新。（有些索引并不是完全非常工整的，最后经过了多次改动了之后，它最后索引有些地方会跨几步，有些地方会少跨或只跨两步，这就是因为里面的一些元素，这就是因为里面的一些元素会被增加和删除，而且它的维护成本相对较高，也就是说当你增加一个元素的话，你会把它的索引要更新一遍，删除一个元素的话，也需要把它的索引都更新一遍，在这种跟新过程中它在增加和删除，它的时间复杂度的话就会变成O(logn)了）。
- 跳表的空间复杂度是O(n)
- 工程中的应用
- LRU Cache - Linked list （最近最少使用算法）Leetcode-LRU缓存机制
- Redis - Skip List
- 知乎L为什么Redis上面用的是跳表而不是红黑树和一些其他高校的二叉树结构。
- 尤其是数组和链表的时间复杂度，他们的增加删除访问的时间复杂度，这个在面试的时候经常会问，而且会根据不同的面试题来考察你用那种数据结构是否考虑的得当。
2. 实战题目解析：移动零
- 练习步骤
- 5-10分钟：读题和思考。
- 有思路：自己直接开始做和写代码，不然，马上看题解。
- 把已经有的题解拿出来背诵，默写直到熟练
- 熟练了之后，第二遍开始自己写（闭卷）不要代码。
实战练习题目 - Array
- move zeros
- 先把所有可能的解法都写出来，先把思路全部都整理出来之后，后面在比较它们得出最好的思路。
- 思路：每次在走的时候就统计0的个数，用一个循环统计0现在有多少个，对于非0元素就往前挪到那些没有0的位置去，那么0的元素就往后面放即可，这样做需要写两个循环。
- 思路：重新开一个新的数组，把所有这些0，如果碰到0就往后放，如果碰到非0就往这个新数组的前面放，也就它有个i，i的话指向数组的头下标，有一个j，j指向新数组的背后，如果非0的话就往这边放，如果是0的话就往j这边放，但这个可能内存空间的话会多。
- 思路：直接在数组中进行index操作，首先直接用最外层的循环就是从i从0循环到nums的length，这是最基本的遍历一维数组。这里的技术处理就是再开一个下标就是j，j记录到非0元素的位置在什么地方，就是要填入的非0元素在什么地方，开始话就是0，下标0表示要是碰到非0元素的话就挪到j去，j的话其实只是0，如果nums[i]等于0的话就不处理，如果nums[i]不等于0，吧nums[i]放到j这个位置，因为j始终记录下一个非0元素要放的位置，如果i不等于j的话，最后把nums[i]赋值为0，接下来在j++。因为这个时候之前非0的元素已经加到j这个位置了，所以j的话位置下标要往后挪一位。
- 这种操作用一个变量j表示新加入的元素要放在什么地方这么一个操作的话，如果不是特别熟练的话，就把这个题目多做几遍。类似于这样的操作就变成了一个小操作或者是大家都熟悉的一种操作即可。
- 写完题之后，执行下自己的代码，系统会把它的标准数据放在这里来跑一遍，还可以更改测试的样例。
- 要养成一个好的习惯，再放一些特殊的结构，全部都是0的情况，或者是一个一个空数组的情况，看会如何解决。
- 一般来说内存可以不用看，主要看时间，时间越快越好。
- 当提交完程序还没完，这是时候永远要记得，如果把它提交了只完成了这一遍的50%，总共是五遍刷题法。
- 后面50%Feedbacks，homework代码提交到GitHub里面去，其他人进行CodeReview。
- 最关键的是要在题解里面看别人的，首先是看官方的，要多看别人的代码，然后把他的师夷长技以制夷自己学过来之后，自己在代码里面改进和写下来。
- 最大误区就是刷题只刷一遍。
- 核心思想就是第一升维，第二要空间换时间。
- 看完国内题解之后，把这个题目的地址复制出来一份，把前面的-cn去掉，去到国际站。
- 国际站进入Discuss里面，按照Most Votes来排序之后，里面有些的非常好的一些代码。
Array 实战题目
3. 实战题目解析：盛水最多的容器、爬楼梯
盛水最多的容器
- 题目解析：它的下标就是它所在的横坐标，它的值就是这柱子的高度，问如果往里面填水的话，它最多可以填多少水。要找的一个就是分得最开的两个柱子，同时它的高度也要足够的高，就导致这里放的水可以最多。
- 一维数组的坐标变换：i 和 j ，然后不断维护i和j来做各种事情。
- 枚举：不管你容器有多，高度有多少，它肯定有个左边界和右边界。
- left bar (x), right bar (y), (x-y)* Max.max(高度最小者)
- 枚举这两个左柱子和右柱子，然后用它的长再乘以它的宽， 叫做高度差。就把x和y枚举，左边称为x，右边称为y，枚举左右边界，把他们的面积用来比较。这个时间复杂度是O(n^2)，因为是一个嵌套的循环进行枚举。
- 涉及到一个遍历数组的一个常见办法，如果要遍历左边界和右边界的话，且左右遍历它本来不能重复。
- 把这一段代码一定要记下来：
- for (int i = 0; i < a.length - 1; ++i)
- for (int j = i + 1; j < a.length; ++j)
- 这样就实现了i和j两个下标对这个数组的一遍遍历，同时保证i和j不会重复，且不会有反复的这么一个值，所以这样是最简化的，两重遍历到这里。
- 接下来按照枚举公式就可以算出，写一个get_Area的函数出来，把i和j放进去，拿到Area之后，每次记录最大的一个值，int max = 0写在外面，一开始max为0，到最内层循环max就是之前上个值的max和area，两个返回最大的值赋值max，最后在return max即可。get_Area如何求？因为j比较的话就是(j-i)再乘以它们的高度中最较小者，因为左棒和右棒它的水肯定是只能堆积在较小的这边，这样就可以求到它的面积。
- 时间复杂度较高。
- 经常用的一个思路：首先，如果我们的左右边界选到最两边的两根棒子的话，它的宽度肯定是最宽的，高度就不一定是最高的了，但是我们可以求这么一点，只要一开始左右两根棒子选在最左边和最右边两个边界，然后再往里面慢慢收敛即可。因为现在宽度是最高了，要选择其他更高的棒子肯定往中间收敛即可。往中间收的话，如果它的高度不及外面的棒子的话，那么就不用再看了，因为里面的这个棒子如果高度都不及外面的，那宽度也肯定不及外面的，里面宽度高度都不及外面的话，面积肯定也不及，就不用看了。只要每次往里面收敛的话，只关注那些棒子更高的。
- 最左边搞一个下标i，最右边搞一个下标j，每次往中间开始收敛，然后计算它的高度，求一个相对高度比较高的棒子，然后算它的面积，最后的话i和j在中间相遇的话，就可以得出结果。这样的办法虽然是用了两个下标i和j，但是没有写嵌套循环，所以它的时间复杂度是O(n)即可解决。
- 每次就是i往右边走，j往左边走，因为它在走的时候，是根据谁高度比较小，谁就往里面继续再挪即可。挪完之后得到一个最小高度，就算它们的面积，最后更新max就会得到所需结果。
- 左右边界中间收敛又叫做左右夹逼的法，一定要记得，是后面解决很多问题的一个基本思路。而不管是循环嵌套的遍历，以及左右向重点收敛的办法，一定要把代码写的滚瓜烂熟。
爬楼梯
- 解题时候反复强调的一种思想：1. 空间换时间、2. 升维升到二维去。
- 解题思路在懵逼的时候要怎么办？如何解决？
- 最关键就是要把它想成什么，先不要想复杂情况，就看一些最基本的情况。
- 首先看能不能暴力求解。
- 最基本的情况应该怎么解决。
- 分析：该题没有特别有效的暴力的方法。
- 台阶总共只有一阶台阶的时候该怎么走？只能走一次，一步跨上去即可。
- 台阶总共只有二阶台阶的时候该怎么走？每次可以走一阶，共走两次，或一下子跨两阶。
- 台阶总共只有三阶台阶的时候该怎么走？每次走一阶，共走三次、或第一次走一阶，第二次走两阶，走两次、或第一次走两阶、第二次走一阶，走两次。
- ….
- 要有一个所谓的递推，也就是说数字归纳法的思想。
- 与其看这个例子把它全部人肉的遍历出来，不如想这么一个想法，这个想法是之前讲过很多次，解决各种问题的话，关键是找 最近 重复的子问题。
- 为什么要找最近 重复的子问题呢？
- 因为我们写程序只能写if else或者是for while 这样的循环，然后就是程序不断调试自己和递归，除了前面if else 这种巨简单的问题之外，其他的情况其实就是for whilee 和 recursion的话都是不断的重复，为什么会这样，就是究其原因，计算机是人类发明的，那么人类能发明出来的工具，肯定没有人脑那么强，它其实就是一个简单的重复式的机器，就是在加上我们现在用的这些程序和用的这些算法都是最简单的算法，所以不涉及任何关于人工智能的东西，就把它想成一个，不断重复在哪里干事情的东西就好，要让它用重复的东西来解决问题说明这个问题本身就是可重复的。后面的回溯，分治，动态规划，递归等，全部都是找重复性。
- 如何找重复性？
- 要上第三级台阶要怎么上去，因为每次只能走一步和每次只能走两步。所以必须从第二级台阶上面跨一步，到第三级台阶来。
- 第一级台阶一下子跨两步跨到第三级台阶来。
- 只有以上两主情况，没有第三种做法，只能从n-1级台阶走过来，或者从n-2 级台阶走过来，
- 第三级台阶的走法，就等于之前第一级的走法，在加上第二级台阶的额走法就可。
- 思路分析：第一台阶的走法有多少种，然后它在这个地方一下子跨两步，就到了第三台阶，或者第二级台阶的走法有多少种，它这时候一下子跨一步，就当了第三级台阶，而且这两个位置的方法的话，因为最后的一步的不同，所以他们肯定不会重复，而且这个办法包含了所有的办法在一起，因为它上了第三阶台阶，只可能最后走一步或者最后走两步，所以的话它就有这么一种关系，那么同理可得，按照数字归纳法，你要上到第n步，你只可能从n - 1 步走过来，或者从n - 2级的台阶一下子跨两步走过去。
- 所以它最后就得到这么一个递推公式，这个递推公式就是Fibonacci数列，那么这个题目其实本质上就是求Fibonacci数列即可。
- 求Fibonacci数列有很多种做法，可以直接写一个递归，但你要是不加任何缓存的话递归的话就是2的n次方的一个傻递归，这里直接写一个循环就行，可以开一个数组就叫 a[n] 的数组写一个循环。
- 实例代码分析：没有用到数组，因为秩序要求最后那个值，直接保存三个变量f1 f2 f3 ，f3 = f1 + f2 ，然后每次再把f1 和 f2更新就行了，也就是说不用一个数组，就保存它的最后三个值，然后不断地往前累加，往前累加即可，就不用把整个中间变量全部保存下来，只需要最近的三个值，然后不断地往后面累出来得到这个答案。
- 程序实现并不难，关键是找到，
- 很多人在看算法和数据结构觉得难，觉得没有思路或者特别沮丧，或者觉得无聊没意思，及时因为基本上没有吧很多文章也好，老师也好，没有把这个思想讲清楚。
- 这里最关键的一种思想就是：
- 第一懵逼的时候要怎么办？
- 想想能不能暴力解。
- 想最简单的问题是什么？
- 一级台阶、二级台阶、三级台阶…想出来之后，就要想怎么泛化，泛化的思路就是找最近重复的子问题。
- 子问题不要找的太远，否则把问题分解成子问题也会非常累。
- 解决所有问题，它的思路就变成一个找重复性。
- 因为程序比较傻，只会做重复的事情。重复的时候可以 if else 分出很多的分支，这样的话就会让所谓的递归程序越来越复杂，它的复杂性就会慢慢这么出来了。
- 关键把将的基本思想多理解， 然后写下来，反复，没事的时候吃饭的时候树胶的时候都去想一想看有没有到底，把这个想明白了之后对计算机、算法的理解是会比旁边的人会更上一层楼的。
4. 实战题目解析：3数之和、环形链表
三数之和
- 先看一个叫做两数之和的问题，这是三数之和的简单版。
- 两数之和题目： https://leetcode-cn.com/problems/two-sum/
- 从数组nums里面找出两个数a和b，使得a + b == target，且可以假定只有一个答案就行，写两重循环就可以了，时间复杂度O(n^2)。
两数之和思路：两重循环枚举不同的下标，枚举这个数组里面出现的a和b，最后看a和b加在一起是否能够等于target。如果是的话即是答案，这就是所谓两数之和的问题。- 三数之和题目：https://leetcode-cn.com/problems/3sum/ (高频老题）
- 三数之和思路：a + b + c = 0 转化-> a + b = -c，其实要做的事情就是找出两个数a和b让他们的和是等于-c的，这里的target其实就是-c。只不过target并不是一个数，它可以是很多数，因为这个-c的话也需要遍历整个nums数组。
- 暴力求解：两重循环来遍历a和b，在外面再加一重循环来遍历target。target就是nums里面的所有元素，再乘以一个-1，就是所谓的target，就额可以直接暴力求解，这办法是需要三重循环，所以时间复杂度是O(n^3)。
- 看题解两数之和如何求解，写两重循环来看，有是否存在两个数，也就是i和j他们的和等于target。
- 看题解三数之和如何求解，第一种暴力求解，现在马上去写一次暴力求解的方法，三重循环来写。（这个看似简单，可以训练对代码的驾驭能力，所以比较重要，一定要自己试着动手写一下）。首先进行一个转换，转换成O(n^2)的解法。
- 用哈希表来记录：其实就是把所有的数都放在哈希表里面去，那么在遍历a和b，遍历出来之后，就直接把a + b的和去和哈希表里面查，看是否之前有负的nums的元素，刚好等于a + b。
- 双指针左右下标：（把左右边界都占了之后，慢慢往中间推进，叫做左右下标中间推进这么一种方式。）
- 这种思路其实严格意义来讲它是非常难以想象的，这种方法就直接看题解，然后把这种方法记下来，这是一种套路题目。把它记住，同时训练熟，下次碰到这个问题的话，要想到利用这样的方法举一反三。
- 这种办法如何求解：三数之和所谓的双指针的办法，双指针的套路一开始必须要做的一件事情，就是先要排序好，没有排序好久没法用双指针左右夹逼的，这是一个前提条件。
- 思路：固定三个指针中最左边数字的指针k，然后首先要固定一个数变成所谓的target，然后它的值也就是负的target。然后在固定这个值右边的这一群数，就用双指针进行查找就行，双指针设为i和j分别设在索引的k 和 nums的length的两端，指的也就是在固定的数右侧，k的话就是它右边最相邻的数，然后nums.length的话就是最右端，然后把i和j的话分别置于它的右侧数组的两端，然后通过双指针交替想中间移动，记录每个固定指针k的所有满足条件的i和j的组合即可。
- 觉得晦涩难懂，认真看下题解的三个步骤，然后再纸上大概画一下，自己要理解，这个其实是一个思维训练体操的过程，就看这个三点思考下，然后再纸上画一下，看能不能理解出来。
- 题解思路：首先将nums进行从小到大排序，排序之后变成最小的在前面，接下来就是枚举k，k就表示固定的一个数，所谓的负target。当k固定之后，i和j分别作为一个双指针，放在k右侧元素的第一个和最后一个上面去，然后再把nums[i]和nums[j]加在一起，和k的元素进行对比，假设i比负k要小的话说明j这个元素偏下了，这两个元素的和，那么就要吧i向右侧移动，因为它是排好序的，所以它的元素的值的大小是从小到大排的，然后将这两个头i和尾j加在一起，如果比target小说明这两值加在一起偏小了，偏小的加要把它加大，如何加大呢？就是i要往右边走，因为这一串元素它是有序的，所以当这两个值小的时候，必须下标i下右移动。如果这两个元素加在一起比target要大的话，那么就把j向里面移动，因为是有序的，左边是最小值，右边是最大值，当i和j两个的和小于target的时候，那么左侧的左边向左移动，否则的话右侧的左边向右移动，直到和j在中间碰撞，或者是找到了nums[i] + [numsj] = k的情况。
- 写完之后一定要看那些好的题解，怎么看好的代码呢？一方面看中文的题解，还有就是去国际站点去，都是算法精英写出来的代码。
- 一定要把这个题目做的滚瓜烂熟，这个双指针的办法，虽然理解起来比较晦涩，学会了之后这种套路其实就是一个定式。
- 这道题目面试的时候，要把暴力求解、哈希表、双指针都先概述一下，以及他们各自方法的时间复杂度也要分析出来，同时一气呵成写出这么一个代码。
Linked List
- 所有的Linked List的题目，第一它解法非常的固定，主要就是熟能生巧，它没有很多算法的东西，关键就是熟悉怎么把next指针换过来换过去，和把prev指针换过来换过去。
- 要熟悉的办法只有一个就是多做，没有任何巧妙的地方，同时还是五遍刷题法一定要做，同时所有Linked List的题目在面试之前一定要再都写一遍这些高频的Linked List 。
- 因为链表题就是有这么一个很让人觉得崩溃的一个地方，它虽然算法很简单很直接，但是它代码一不小心的话就会写的非常复杂，所以一定要注意。
- 反转链表：给你一个链表把它进行反转，关键就是怎么操作这个链表。
- 写完之后看下别人的代码，看看自己的代码是否简洁，把自己代码修改简洁。
- 所以链表的题目基本上就是死的，唯一的有一个题目就是环形链表，这个题目在思维上稍微有一点巧妙性在里面。
- https://leetcode.com/problems/linked-list-cycle
- 给定一个链表，判断链表中是否有环。
- 什么是环？就是next又指向了之前这个链表里面的一个元素，这就是一个环。
- 解法一暴力法
- 遍历这个链表，遍历过程中还要用哈希表或者set也都是一样的。记录下来访问过的所有节点，把它记录到set里面或者记录在哈希表里面去，然后看接下来后面的元素在新访问的元素有没有出现在这个set里面，表示又走回到原来的老节点去了，那就说明有环了。
- 解法二快慢指针
- 所谓的这种环形链表的题目，有一个比较套路的地方，就是用快慢指针。
- 这个题目最后面有一个进阶，问是否能用O(1)的办法解决此问题。
- 现实中实用性不强，工程上不会出现这种问题，所以当成一个思维训练。
- 官方题解：
- 哈希表：把所有访问过的节点放到哈希set里面去即可。
- 双指针： 官方叫双指针其实更加适合的叫法为快慢指针，就是指针a和指针b都是从头开始跑，但是一个指针每次动一次，另外一个指针每次动两次，类似龟兔赛跑的过程，乌龟要跑的慢，而兔子要跑的快，这样如果只要有环的话，那么快的肯定会套圈慢的，这样就搞一个慢指针和一个快指针，慢指针每次动一步，快指针每次动两步，最后看快指针和慢指针是否重叠在一起了，如果重叠的话就有环，没有重叠的话就没有环。
- 自己想出这个办法基本上不可能，所以直接看题解学会这种办法，而不要发明创造。尤其是高级的算法数据结构，如能能发明创造出来，基本上是图灵奖选手。所以只要学习和学会使用即可。
第1周-第4课 | 栈、队列、优先队列、双端队列
###1. 栈和队列的实现与特性
- 作业：用这套新的API把Deque示例代码程序改写。
- 作业：分析Queue和Priority Queue的源码。
- https://leetcode.com/problems/design-circular-deque
- https://leetcode.com/problems/trapping-rain-water/