0-思路
算法中第一次提一下，当解一个题目的时候，拿到题目如果没有思路，那就回顾一下数据结构和常用的算法，如：数组、链表、队栈、Hash、集合、树、堆；查找、排序、双指针、递归、迭代、分治、贪心、回溯和动态规划等。（不要一开始就力求找到一个最好的解决办法，可以把自己的思考过程也说出来和面试官交流）
1-链表
- 🐍 单链表
- 特征：
元素分散存储、每个元素唯一指针指向唯一后继 - 两种形式：
带头节点和不带头节点 - 增删改查：单链表的这些操作比较简单，找得到头，就能很方便的“查”和“改”，“增”和“删”注意一下指针断开的顺序即可，“增”有尾插法和头插法
- 特征：
- 根据最基本的单链表延申出来的有：
🧬双链表、🧣循环单链表（头尾相连）、🪢循环双链表。链表的重点在于注重操作指针时的断开顺序，防止丢链
2-链表面试题
2.1-两个链表第一个公共子节点
题目：找出两个链表的第一个公共节点。剑指 Offer 52. 两个链表的第一个公共节点
- 🧠 思路演进
1>暴力解决：两个链表，两层循环嵌套，找到相等的那一个就是第一个公共节点2>Hash&集合：先将一个链表遍历一遍，放入Map或者集合中，再遍历第二个链表，如果Map或集合中有，这就是我们要找的公共节点3>栈：先回顾单链表的特点（每个节点只有一个后继），所以这个题给出的链表一定是合流的形式，合流之后不可能再分流，因为分流意味着一个节点有了多个后继，就不符合单链表的定义了。所以反过来，从链表的尾往前找，最后一个相等的就是第一个公共节点，虽然链表只能从前访问，但栈提供了后进先访问的特点4>⭐⭐⭐思考一下，我们之所以不能用两个指针同时遍历然后判断相等来找这第一个公共子节点，其原因在于两个链表长度不一样，按照同样的步长遍历，无法同时到达第一个公共子节点，所以，只要指针能同时到第一个公共子节点，也可以解决这个问题- 拼接链表：A→B == B→A，这样长度就相同了，然后遍历，一定可以同时到达第一个公共子节点，实际代码过程中不用真的拼接，一个指针按 AB 的顺序遍历，另一个指针按 BA 的顺序遍历即可，两个指针相等时，该节点就是第一个公共子节点
- 差分指针：长的链表长多少，就先走多少步，这样两个指针就可以同时到了
2.2-判断链表是不是回文序列
题目：判断链表是不是回文序列 234. 回文链表
- 🧠 思路演进
- 此题思路较多，回文序列，特点倒过来也还是一样的，所以可以使用栈赋予链表倒着遍历的能力，然后比较相同即可
- ⭐双指针思想中的快慢指针：慢指针每次走一步，快指针每次走两步，这样快指针到表尾时，慢指针到中间，慢指针走的时候压入栈，到中间之后一边向后继续走，一边和出栈比较；或者到中间后逆序一半元素再比较，这样的话不用栈空间复杂度就不高（不用先遍历一遍得到链表的长度）
2.3-合并链表
- 🧠 题型思考
1>合并两个链表 21. 合并两个有序链表，很简单，比较，移动，其中一个合并完后，剩下的直接接到新链表的末尾即可2>合并 K 个链表，如果想一次成型，当然可以多条都一起比较，也可以用到堆、归并等内容。但不考虑一次成型，基于我们已经会将两个链表合并，就可以两两合并得到最后结果，这样稳妥且容易
2.4-双指针专题
- 🧠 题型思考
1>找链表中间节点 876. 链表的中间结点，这个前面也提到了，可以用快慢双指针（补充一个注意点，循环走的过程中，判断的条件不仅为快指针不为空，还要快指针的 next 也不为空，不然当链表为奇数个，快指针已经在表尾，没有第二个条件的话还会继续走一轮）2>寻找链表倒数第K个元素：其实这种需要从后数的，可以用栈赋予链表这个能力，此外，也可以用间隔K个元素的双指针遍历找到，额外需要考虑一下链表是否有 K 那么长3>旋转链表：将链表每个节点向右移动 k 个位置。除了可以按题意进行移动，变相理解后也就是将表尾K个元素放到前面去，所以变相也是第二个问题，需要稍微注意一下的是可能给的 K 比链表长度还长，这个时候计算一下取余数即可- 🎏链表逆序，可以用栈，可以用多指针遍历两遍等方法
2.5-删除链表元素专题
- 🧠 题型思考
1>普通的删节点比较基础，删倒数第 k 个节点可以当前面双指针基础上来的2>直接给定了链表中的某个节点，要求删除 203. 移除链表元素。直观来看需要将前一个节点指到后一个节点上去完成删除，但此时因为单链表的特点，无法找到前一个节点，所以可以将后一个节点的值复制到当前节点，然后正常删除后一个节点即可，效果是一样的3>有序链表删除重复元素：遍历一遍，按序加入与新链表表尾元素不相同的节点即可- 🎏无序链表删除重复元素：如果排序后再删除复杂度较高，这个时候可以考虑 HashMap 和集合
2.6-链表中的环问题
题目：简单问，是否有环 141. 环形链表，深一步，环的入口在哪 142. 环形链表 II
- 🧠 题型思考
1>HashMap与集合 解决这个问题最简单，只要撞到，那么就有环，第一个撞到的就是环的入口2>快慢双指针：这里使用这个解决问题是用数学，因为只要有环，两个指针一定会相遇，通过数学求解，发现 头节点与相遇的这个节点到环的入口节点距离相等，知道这个结论在知道相遇节点后用两个指针同步跑一下即可找到环的入口