深圳本地招聘网站,网易企业邮箱后缀,餐饮公司注册条件,承德信息网招聘信息算法通关村第一关–链表白银挑战笔记 开始时间#xff1a;2023年7月18日14:39:36 链表
Java中定义一个链表 class ListNode {public int val;public ListNode next;ListNode(int x) {val x;next null;}}1、四种方法解决两个链表第一个公共子节点
解释一下什么是公共节点 如…算法通关村第一关–链表白银挑战笔记 开始时间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
链表Bs-e-8-7
拼接 AB 、BA
AB0-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_aleft_b和right_b这样四个部分并且right_a和right_b是一样的这时候我们拼接AB和BA就是这样的结构
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XEcYRetf-1690265452152)(链表_面试高频题.assets/1688482919103-da7b4f0a-fdf5-473e-9825-ff8ef174e103.png)]
第四种差和双指针
我们再看另一个使用差和双指针来解决问题的方法。假如公共子节点一定存在第一轮遍历假设La长度为L1Lb长度为L2.则L2-L1就是两个的差值。第二轮遍历长的先走L2-L1,然后两个链表同时向前走结点一样的时候就是公共结点了。
public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {if(pHead1null || pHead2null){return null;}ListNode current1pHead1;ListNode current2pHead2;int l10,l20;//分别统计两个链表的长度while(current1!null){current1current1.next;l1;}while(current2!null){current2current2.next;l2;}current1pHead1;current2pHead2;int subl1l2?l1-l2:l2-l1;//长的先走sub步if(l1l2){int a0;while(asub){current1current1.next;a;} }if(l1l2){int a0;while(asub){current2current2.next;a;} }//同时遍历两个链表while(current2!current1){current2current2.next;current1current1.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按照升序合并成一个链表。2list2也将区间[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、删除链表元素专题 结束时间
