白银挑战——链表高频面试算法题
算法通关村第一关–链表白银挑战笔记
开始时间：2023年7月18日14:39:36
链表
Java中定义一个链表
class ListNode {
public int val;
public ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
1、四种方法解决两个链表第一个公共子节点
解释一下什么是公共节点 如图，从3节点开始就是第一个公共子节点，也就是说我们要找到这个节点，有一下方式。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4bUTJyWi-1690265452150)(链表_面试高频题.assetsimage-20230724153946551.png)]
第一种：哈希和集合
思想就是使用遍历的思想进行查找，将链表的数据全部放入两个Map，一个Map 做遍历的操作，另个就和它对比，相等的点一定是第一个公共节点。这样就能找到。
第二种：使用栈
这里需要使用两个栈，分别将两个链表的结点入两个栈，然后分别出栈，如果相等就继续出栈，一直找到最晚出栈的那一组。这种方式需要两个O(n)的空间，所以在面试时不占优势，但是能够很好锻炼我们的基础能力。
第三种：拼接两个字符串
链表A ：0-1-2-3-8-7
链表B：s-e-8-7
拼接 AB 、BA
AB：0-1-2-3-8-9-s-e-8-7
BA : s-e-8-7-0-1-2-3-8-9
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y8dYSX09-1690265452152)(链表_面试高频题.assets/image-20230725112957058.png)]
我们发现拼接后从最后的8开始，两个链表是一样的了，自然8就是要找的节点，所以可以通过拼接的方式来寻找交点。这么做的道理是什么呢？我们可以从几何的角度来分析。我们假定A和B有相交的位置，以交点为中心，可以将两个链表分别分为left_a和right_a，left_b和right_b这样四个部分，并且right_a和right_b是一样的，这时候我们拼接AB和BA就是这样的结构：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XEcYRetf-1690265452152)(链表_面试高频题.assets/1688482919103-da7b4f0a-fdf5-473e-9825-ff8ef174e103.png)]
第四种：差和双指针
我们再看另一个使用差和双指针来解决问题的方法。假如公共子节点一定存在第一轮遍历，假设La长度为L1，Lb长度为L2.则｜L2-L1｜就是两个的差值。第二轮遍历，长的先走｜L2-L1｜,然后两个链表同时向前走，结点一样的时候就是公共结点了。
public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null){
return null;
}
ListNode current1=pHead1;
ListNode current2=pHead2;
int l1=0,l2=0;
//分别统计两个链表的长度
while(current1!=null){
current1=current1.next;
l1++;
}
while(current2!=null){
current2=current2.next;
l2++;
}
current1=pHead1;
current2=pHead2;
int sub=l1>l2?l1-l2:l2-l1;
//长的先走sub步
if(l1>l2){
int a=0;
while(a<sub){
current1=current1.next;
a++;
}
}
if(l1<l2){
int a=0;
while(a<sub){
current2=current2.next;
a++;
}
}
//同时遍历两个链表
while(current2!=current1){
current2=current2.next;
current1=current1.next;
}
return current1;
}
2、判断链表是否为回文序列
什么是回文序列 如图所示：简单理解就就是对称
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QBgv6d4C-1690265452153)(链表_面试高频题.assets/image-20230724155012538.png)]
方法1：将链表元素都赋值到数组中，然后可以从数组两端向中间对比。这种方法会被视为逃避链表，面试不能这么干。
方法2：将链表元素全部压栈，然后一边出栈，一边重新遍历链表，一边比较两者元素值，只要有一个不相等，那就不是。
方法3：优化方法2，先遍历第一遍，得到总长度。之后一边遍历链表，一边压栈。到达链表长度一半后就不再压栈，而是一边出栈，一边遍历，一边比较，只要有一个不相等，就不是回文链表。这样可以节省一半的空间。
方法4：优化方法3：既然要得到长度，那还是要遍历一次链表才可以，那是不是可以一边遍历一边全部压栈，然后第二遍比较的时候，只比较一半的元素呢？也就是只有一半的元素出栈， 链表也只遍历一半，当然可以。
方法5：反转链表法， 先创建一个链表newList，将原始链表oldList的元素值逆序保存到newList中，然后重新一边遍历两个链表，一遍比较元素的值，只要有一个位置的元素值不一样，就不是回文链表。
方法6：优化方法5，我们只反转一半的元素就行了。先遍历一遍，得到总长度。然后重新遍历，到达一半的位置后不再反转，就开始比较两个链表。
方法7：优化方法6，我们使用双指针思想里的快慢指针 ，fast一次走两步，slow一次走一步。当fast到达表尾的时候，slow正好到达一半的位置，那么接下来可以从头开始逆序一半的元素，或者从slow开始逆序一半的元素，都可以。
方法8：在遍历的时候使用递归来反转一半链表可以吗？当然可以，再组合一下我们还能想出更多的方法，解决问题的思路不止这些了，此时单纯增加解法数量没啥意义了。
3、合并有序链表
3.1 合并两个有序链表
LeetCode21 将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。
解决思路就是 新建一个链，再通过比较那个两个需要排序链，小的就放进来，这样就可以达到题目要求。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode(-1);
ListNode res = newHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
newHead.next = list1;
list1 = list1.next;
} else if (list1.val > list2.val) {
newHead.next = list2;
list2 = list2.next;
} else { //相等的情况，分别接两个链
newHead.next = list2;
list2 = list2.next;
newHead = newHead.next;
newHead.next = list1;
list1 = list1.next;
}
newHead = newHead.next;
}
//下面的两个while最多只有一个会执行
while (list1 != null) {
newHead.next = list1;
list1 = list1.next;
newHead = newHead.next;
}
while (list2 != null) {
newHead.next = list2;
list2 = list2.next;
newHead = newHead.next;
}
return res.next;
}
优化
进一步分析，我们发现两个继续优化的点，一个是上面第一个大while里有三种情况，我们可以将其合并成两个，如果两个链表存在相同元素，第一次出现时使用if (l1.val <= l2.val)来处理，后面一次则会被else处理掉，什么意思呢？我们看一个序列。
假如list1为{1, 5, 8, 12}，list2为{2, 5, 9, 13}，此时都有一个node(5)。当两个链表都到5的位置时，出现了list1.val == list2.val，此时list1中的node(5)会被合并进来。然后list1继续向前走到了node(8)，此时list2还是node(5)，因此就会执行else中的代码块。这样就可以将第一个while的代码从三种变成两种，精简了很多。
第二个优化是后面两个小的while循环，这两个while最多只有一个会执行，而且由于链表只要将链表头接好，后面的自然就接上了，因此循环都不用写，也就是这样：
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
prev.next = list1;
list1 = list1.next;
} else {
prev.next = list2;
list2 = list2.next;
}
prev = prev.next;
}
// 最多只有一个还未被合并完，直接接上去就行了,这是链表合并比数组合并方便的地方
prev.next = list1 == null ? list2 : list1;
return prehead.next;
}
3.2 合并K个链表
合并k个链表，有多种方式，例如堆、归并等等。如果面试遇到，我倾向先将前两个合并，之后再将后面的逐步合并进来，这样的的好处是只要将两个合并的写清楚，合并K个就容易很多，现场写最稳妥：
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = null;
for (ListNode list: lists) {
res = mergeTwoLists(res, list);
}
return res;
}
3.3 一道很无聊的好题
LeetCode1669：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中下标从a到b的节点删除，并将list2 接在被删除节点的位置。
1669题的意思就是将list1中的[a,b]区间的删掉，然后将list2接进去，你觉得难吗？如果这也是算法的话，我至少可以造出七八道题，例如：（1）定义list1的[a,b]区间为list3，将list3和list2按照升序合并成一个链表。（2）list2也将区间[a,b]的元素删掉，然后将list1和list2合并成一个链表。（3）定义list2的[a,b]区间为list4，将list2和list4合并成有序链表。
看到了吗？掌握基础是多么重要，我们自己都能造出题目来。这也是为什么算法会越刷越少，因为到后面会发现套路就这样，花样随便变，以不变应万变就是我们的宗旨。
具体到这个题，按部就班遍历找到链表1保留部分的尾节点和链表2的尾节点，将两链表连接起来就行了。
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode pre1 = list1, post1 = list1, post2 = list2;
int i = 0, j = 0;
while(pre1 != null && post1 != null && j < b){
if(i != a - 1){
pre1 = pre1.next;
i++;
}
if(j != b){
post1 = post1.next;
j++;
}
}
post1 = post1.next;
//寻找list2的尾节点
while(post2.next != null){
post2 = post2.next;
}
//链1尾接链2头，链2尾接链1后半部分的头
pre1.next = list2;
post2.next = post1;
return list1;
}
4、双指针专题
5、删除链表元素专题
节点
while(post2.next != null){
post2 = post2.next;
}
//链1尾接链2头，链2尾接链1后半部分的头
pre1.next = list2;
post2.next = post1;
return list1;
}
## 4、双指针专题
## 5、删除链表元素专题
> 结束时间：