算法通关村第一关–链表白银挑战笔记

开始时间：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)(链表_面试高频题.assets\image-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、删除链表元素专题> 结束时间：