做视频网站用什么开发,自学编程,快速网站仿制,wordpress 新闻资讯目录
1.❤️❤️前言~#x1f973;#x1f389;#x1f389;#x1f389;
2.反转一个单链表
3. 找到链表的中间节点
4.输入一个链表#xff0c;输出该链表中倒数第k个结点。 5.合并两个有序链表
6.链表分割
7. 判定链表的回文结构
8.输入两个链表#xff0c;找…
目录
1.❤️❤️前言~
2.反转一个单链表
3. 找到链表的中间节点
4.输入一个链表输出该链表中倒数第k个结点。 5.合并两个有序链表
6.链表分割
7. 判定链表的回文结构
8.输入两个链表找出它们的第一个公共结点。
9. 判断链表中是否有环
10.返回链表开始入环的第一个节点 11.总结 1.❤️❤️前言~ Hello, Hello~ 亲爱的朋友们这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章请别吝啬你的点赞❤️❤️和收藏。如果你对我的内容感兴趣记得关注我以便不错过每一篇精彩。 当然如果在阅读中发现任何问题或疑问我非常欢迎你在评论区留言指正️️。让我们共同努力一起进步 加油一起CHIN UP 个人主页E绵绵的博客 所属专栏 1. JAVA知识点专栏 深入探索JAVA的核心概念与技术细节 2.JAVA题目练习 实战演练巩固JAVA编程技能 3.c语言知识点专栏 揭示c语言的底层逻辑与高级特性 4.c语言题目练习 挑战自我提升c语言编程能力 持续更新中敬请期待❤️❤️ 这篇文章我们将给大家带来一些单链表的面试题都很有意思来看一下吧。 2.反转一个单链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 我们的解决方法是依次头插法 最开始时我们需要将第一个节点的next值变为null使其变成最后的节点就产生了新的链表。而后依次将原始链表中的第二个节点第三个节点直至最后一个节点头插到新链表中。 这样就翻转成功了 完整代码如下 public void reverseList() {if(headnull)return;ListNode curhead.next;ListNode prev;head.nextnull;while(cur!null){prevcur.next;cur.nexthead;headcur;curprev;}} 这是该题的链接 翻转链表
3. 找到链表的中间节点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 该题的思路实现是设置两个引用slow 慢引用 和 fast 快引用 fast 和 slow 同时从head开始遍历但是fast一次走两步slow一次只走一步最后我们会发现当 fast遍历完成后 对应的slow正好是链表的中间节点或者第二个中间节点。 fast遍历完成的标志是fast.nextnull或者fastnull 完整代码如下 public ListNode middleNode(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}return slow;
} 该题链接求链表中间结点
4.输入一个链表输出该链表中倒数第k个结点。 该题有两种思路 第一种思路 第二种思路 所以我们采用第二种思路去做题且我们还需要注意k的合法性。 整体代码如下 public ListNode FindKthToTail(ListNode head,int k){
if(headnull){
return null;
}
ListNode fast head;
ListNode slow head;
//1.判断k值的合法性
if( k0 ){
System.out.println(k值不合法);
return null;
}
//2.让fast 提前走 k-1 步
while(k-10){
if(fast null |l fast.next null){
System.out.println(k值不合法”);
return null;
}
fast fast.next;
k--;
}
while(fast !null fast.next ! null){
fast fast.next;slow slow.next;
return slow;
}
} 该题题目已下架无链接。 5.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路 1.先创建一个新的链表 2.让cur1 和 cur2遍历两个链表遇到的节点逐个比较将值小的节点往新链表的末尾tail进行尾插 3.上述循环结束后要判断有无链表还有剩余元素把剩余的元素尾插到新链表的末尾。 完整代码如下 public static ListNode mergeTwoLists(ListNode list1, ListNode list2){//将两个有序链表合并为一个有序链表ListNode head1list1;ListNode head2list2;ListNode headnew ListNode(-1);ListNode curhead;while(head1!nullhead2!null){if(head1.valuehead2.value){cur.nexthead2;curcur.next;head2head2.next;}else{cur.nexthead1;curcur.next;head1head1.next;}}while(head1!null){cur.nexthead1;curcur.next;head1head1.next;}while(head2!null){cur.nexthead2;curcur.next;head2head2.next;}return head.next;} 该题链接合并两个有序链表
6.链表分割 现有一链表的头引用 pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 解题思路 1.创建两个链表一个链表尾插值小于x的节点另一个链表中插值大于等于x的节点 2.遍历原链表将链表中的节点往两个新链表中尾插 3.将两个链表拼接 但是这种思路仍然存在较大的问题什么问题呢? 1.我们传入的x值比节点中val都大或者都小那么存在一个问题就是有一个链表中的内容为空那么按照上面的思路走时必然会出现空指针异常的情况。 解决方法: 当第一个区间为空时,那么直接返回ca 2.最后一个节点分到小于x的区间那么最后一个节点的next并不是null所以此时我们必须手动将 cb.nextnull; 预防最后一个节点的next不是null从而报错。 完整代码如下 public static ListNode partition(ListNode pHead, int x) {//给一定值x该方法将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。if(pHeadnull)return null;ListNode curpHead;ListNode sanull;ListNode sbnull; //小于x的结点所在链表ListNode canull;ListNode cbnull; //大于x的结点所在链表while(cur!null){if(cur.valuex){if(sanull){sacur;sbcur;curcur.next;}else{sb.nextcur;sbcur;curcur.next;}}else{if(canull){cacur;cbcur;curcur.next;}else{cb.nextcur;cbcur;curcur.next;} }}//拼接两个链表if(sanull)return ca;//如果不存在小于X的结点则直接返回大于x的链表否则按如下执行会报错if(ca!null)cb.nextnull;//将链表中的最后一个结点的next值变为null防止其循环从而报错sb.nextca;return sa;} 题目链接链表分割_牛客题霸_牛客网
7. 判定链表的回文结构 解题思路实现 1.找到链表的中间节点找中间节点:采用快慢指针就行了 2.对链表的后半部分进行反转 3.将两个链表从前往后逐个节点进行比对如果比对之后发现所有节点的值域都相同则是回文链表否则不是. 并且在循环时还需注意当链表为奇数或偶数时判定循环结束的标志不同 奇数是headslow时结束 偶数是head.nextslow时结束 所以完整代码如下 public static boolean checkPalindrome(ListNode A) {//判断链表是否为回文结构if(Anull||A.nextnull)return true;ListNode slowA;ListNode fastA;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}ListNode curslow.next;while(cur!null){ListNode curnextcur.next;cur.nextslow;slowcur;curcurnext;}ListNode headA;while(head!slow){if(head.value!slow.value)return false;if(head.nextslow)return true;headhead.next;slowslow.next;}return true;} 注意:在执行完该方法后链表结构会被破坏掉之后如果还对该链表进行操作结果会和我们预想的结果不一样。 该题链接链表的回文结构_牛客题霸_牛客网
8.输入两个链表找出它们的第一个公共结点。 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 下面是两个节点相交的各类情况 从上述链表相交的情况看出两个单链表只要相交从交点开始到其后续所有的节点都是两个链表中公共的节点检测两个链表是否相交:分别找到两个链表中的最后一个节点然后检测这两个节点的地址是否相同即可如果地址相同则相交否则不相交 解题思路 1.让较长的链表先走两个链表的差值步数 2.再让两个链表同时往后走直到遇到地址相同的交点没有则返回null public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {//给你两个单链表的头节点 headA 和 headB 找出并返回两个单链表相交的起始节点。if(headAnull||headBnull)return null;ListNode cur1headA;ListNode cur2headB;int length10;int length20;while(cur1!null){length1;cur1cur1.next;}while(cur2!null){length2;cur2cur2.next;}cur1headA;cur2headB;if(length1length2){for(int i0;ilength1-length2;i){cur1cur1.next;}}else{for(int i0;ilength2-length1;i){cur2cur2.next;}}while(cur1!null){if(cur1cur2)return cur1;cur1cur1.next;cur2cur2.next;}return null;}题目链接找出两个链表的第一个公共节点
9. 判断链表中是否有环 给你一个链表的头节点 head 判断链表中是否有环。 解题思路 设计快慢指针去解决即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。 扩展问题 1.为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现始终相遇不到的情况因此在慢指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。 2.快指针一次走3步走4步...n步行吗 假设:快指针每次走3步满指针每次走一步此时快指针肯定先进环慢指针后来才进环。假设慢指针进环时候快指针的位置如图所示: 此时按照上述方法来绕环移动每次快指针走3步慢指针走1步它们是永远不会相遇的因此不行。 只有快指针走2步慢指针走一步才可以因为每移动一次它们之间的距离就缩小一步无论如何都能相遇。 所以我们在环问题中设置快慢指针都是将快指针设置为一次两步慢指针一次一步这样当存在圈时无论如何都会相遇。 完整代码如下 public static boolean hasCycle(ListNode head) {//给你一个链表的头节点 head 判断链表中是否有环。if(headnull||head.nextnull)//只有一个节点时默认绝对不存在环return false;ListNode slowhead;ListNode fasthead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(slowfast)return true;}return false;}题目链接 判断链表中是否有环
10.返回链表开始入环的第一个节点 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 解题思路 设计一个慢指针一个快指针快指针一次两步慢指针一次一步。使两指针相遇而后让一个指针从链表起始位置开始遍历链表同时也让一个指针从相遇点的位置开始绕环运行两个指针都是每次均走一步最终肯定会在入口点的位置相遇。 它们肯定会在入口点相遇的证明如下 上图中的H为链表的起始点E为环入口点M为慢速指针相遇点设环的长度为RH到E的距离为L E到M的距离为X则M到E的距离为R-X 在快慢指针相遇过程时快慢指针相遇时所走的路径长度:fast:L X nR slow:L X 注意: 1.当慢指针进入环时快指针可能已经在环中绕了n圈了n至少为1。 因为:快指针先进环走到M的位置最后又在M的位置与慢指针相遇 2.慢指针进环之后快指针肯定会在慢指针走一圈之内追上慢指针 因为:慢指针进环后快慢指针之间的距离最多就是环的长度而两个指针在移动时每次它们至今的距离都缩减一步因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的 而快指针速度是满指针的两倍。 所以有如下关系是: 2 *(LX)LXnR LXnR LnR-X(n为1,2,3,4..……n的大小取决于环的大小环越小n越大) 极端情况下假设n1此时:LR-X 所以由此得知一个指针从链表起始位置运行一个指针从相遇点位置绕环每次都走一步两个指针无论如何最终都会在入口点的位置相遇。 完整代码如下 public static ListNode detectCycle(ListNode head) {//给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。if(headnull||head.nextnull)return null;ListNode slowhead;ListNode fasthead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(slowfast){slowhead;while(slow!fast){slowslow.next;fastfast.next;}return slow;}}return null;} 11.总结 所以对于这10个面试题我们就讲述清楚了并且我还把其中的部分题目当作特殊方法加入到模拟的无头单向非循环链表类中。 对于该无头单向非循环链表的模拟实现和其具体使用放到码云里了大家可以看下无头单向非循环链表的模拟实现和其具体使用(此外还往模拟的链表内部添加了一些特殊方法) 下篇文章将给大家带来LinkedList的模拟实现和具体使用。 在此我们诚挚地邀请各位大佬们为我们点赞、关注并在评论区留下您宝贵的意见与建议。让我们共同学习共同进步为知识的海洋增添更多宝贵的财富❤️❤️
