摘要:构建双指针距离前指针先向前走步结束后,双指针和间相距步。它们起始都位于链表的头部。随后,指针每次向后移动一个位置,而指针向后移动两个位置。
题目:
解题思路:
如下图,我们要实现的就是这样一个效果
要实现上图的效果,需要以下步骤:
①设置两个指针,cur 指向链表头节点,prev 指向空
②暂存 cur 的后继节点,curNext = cur.next
③将 cur.next 反指向prev(一开始prev为空)
④prev 指针后移,即将 prev 指向 cur
⑤cur 指针后移 ,即将 cur 指向 2 中暂存的 curNext 节点
⑥循环: 第2 到 5 步,直到 cur 遍历完整个链表/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution { public ListNode reverseList(ListNode head) { if(head==null){ System.out.println("链表为空"); } //设置两个指针,cur 指向链表头节点,prev 指向空 ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode curNext = cur.next;//暂存 cur 的后继节点,curNext = cur.next cur.next =prev;//将 cur.next 反指向prev(一开始prev为空) prev = cur;//prev 指针后移,即将 prev 指向 cur cur = curNext;//cur 指针后移 ,即将 cur 指向 2 中暂存的 curNext 节点 }//循环: 第2 到 5 步,直到 cur 遍历完整个链表 return prev; }}
题目:
解题思路:
本题用的是双指针的方法
①分别设置一个快指针和一个慢指针
②快指针每次走两步,慢指针每次走一步
③当快指针走到最后尾节点的时候,慢指针就走到了链表中间节点/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head;//快指针一开始指向头结点 ListNode slow = head;//慢指针一开始也指向头结点 while(fast!=null&&fast.next!=null){//由于要考虑偶数链表返回中间靠后的节点 //所以要多设置一个fast.next!=null条件 fast=fast.next.next;//快指针往后走两步 slow=slow.next;//慢指针往后走一步 } return slow;//返回慢指针 }}
题目:
解题思路:
这题和上题一样,采用双指针的办法,遍历链表一次就能达到目的
具体需要以下步骤:
①初始化: 前指针 former 、后指针 latter ,双指针都指向头节点 head 。
②构建双指针距离: 前指针 former 先向前走 k-1 步(结束后,双指针 former 和 latter 间相距 k-1步)。
③双指针共同移动: 循环中,双指针 former 和 latter 每轮都向前走一步,直至 former 走到链表 尾节点 时跳出(跳出后, latter 与尾节点距离为 k-1步,即 latter 指向倒数第 k 个节点)
④返回值: 返回 latter 即可。/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode former = head;//设置一个先行节点,一开始指向头结点 ListNode latter = head;//再设置一个后行节点,一开始指向头结点 for(int i=1; i < k; i++){//构建双节点之间距离 former = former.next;// } //构建距离完成之后,双节点同时向后走,直至先行节点到达尾节点处 while(former.next!=null){// former = former.next;// latter = latter.next;// } return latter;//此时latter距离尾节点k-1步,也就是指向倒数第k个节点,直接返回latter即可 }}
题目:
解题思路:
具体步骤如下
①设置傀儡节点,傀儡节点后边的节点组成的链表就是合并后的链表
②比较两个链表的每个节点,存入傀儡节点后的合并链表
③当有一条链已经遍历完成则将另一条链接到合并链表的尾部
④最后返回的是傀儡节点的下一个节点,这才是合并后的链表的头结点/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode newhead = new ListNode(-1);//创建一个虚拟傀儡节点,最后返回的是.next ListNode tmp =newhead;//创建局部引用,指向傀儡节点 while (l1!=null && l2!=null) {//依次比较节点 if (l1.val < l2.val) {//情况1 tmp.next = l1;//将节点存入合并链表 l1 = l1.next;//L2往后走一步 tmp = tmp.next;//合并链表也要往后走一步好用于储存下一个比较结果 } else { //情况2 tmp.next = l2;//将节点存入合并链表 l2 = l2.next;//L2往后走一步 tmp = tmp.next;//合并链表也要往后走一步好用于储存下一个比较结果 } } if (l1==null){//当第一条链先走完 tmp.next = l2;//将第二条链接到合并链表后 } if (l2==null){//当第二条链先走完 tmp.next = l1;//将第一条链接到合并链表后 } return newhead.next;//最终返回傀儡节点的下一个节点,也就是合并链表的头结点}
题目:
解题思路:
①本题用的双链表的方法,分别写一个A链表和B链表,A链表放值小于X的节点,B链表放值大于X的节点,依次遍历原链表就行了
②不过要注意一个关键点,遍历结束后,我们将 L2 的next指针置空,这是因为当前节点复用的是原链表的节点,而其 指针可能指向一个小于 xx 的节点,我们需要切断这个引用
③最后将两个链表合成一个链表即可 (L1.next指向B.next就可以了)/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution { public ListNode partition(ListNode head, int x) { ListNode headA=new ListNode();//设置一个傀儡节点A,代表A链表 ListNode headB=new ListNode();//再设置一个傀儡节点B,代表B表 ListNode l1 = headA;//局部引用l1 ListNode l2 = headB;//局部引用l2 ListNode cur= head;//局部引用cur while(cur!=null){//遍历原链表 if(cur.val<x){//小于X放A l1.next=cur; l1=l1.next; }else{ //大于X放B l2.next=cur; l2=l2.next; } cur=cur.next;//依次遍历 } l2.next=null;//遍历结束后,我们将 l2 的next指针置空 //这是因为当前节点复用的是原链表的节点,而其指针可能指向一个小于 xx 的节点 //我们需要切断这个引用 l1.next=headB.next;//链接两个链表,A的尾巴指向B的头 return headA.next;//返回A的next,因为第一个节点其实是傀儡节点 //第二个开始才是A链表的头结点 }}
题目:
解题思路:
主要思想就是遍历原链表,将不重复的节点提取出来放到一个新的链表里
①遍历原链表(利用临时变量cur代替头结点)
②创建一个新头结点,代表一个新链表
③判断当前节点与下一个节点是否相同,如果相同则cur往后走一步,不同则将此节点存入新节点
④返回新头结点的下一节点(新头结点其实是傀儡节点,新链表其实是从第二个节点开始的)public ListNode deleteDuplicates(ListNode head) { ListNode cur = head;//设置临时变量代替头结点遍历原链表 ListNode newHead = new ListNode(-1);//创建一个新头结点代表一个新的链表 ListNode tmp = newHead;//设置临时变量代替新链表的头结点 while (cur != null) {//设置终止条件 if (cur.next != null && cur.val == cur.next.val) { //判断当前节点值是否等于下一个节点 //前提是下一个节点不为null,不然会有空指针导致访问异常 while (cur.next != null && cur.val == cur.next.val) { //这里还需要考虑到有两个以上重复的节点怎么处理 //所以还需要一个while来跳过重复节点 cur = cur.next; } cur = cur.next;//往后多走一步,因为题目要求不需要保留重复节点 } else {//不满足等值条件的点,直接跳过,往后遍历即可 tmp.next = cur; tmp = tmp.next; cur = cur.next; } } //防止最后一个节点值也是重复的 tmp.next = null;//因为cur是原链表的引用,后边还会指向原链表中的节点 //所以要置空,只保留当时cur指向的那个节点 return newHead.next; }
题目:
解题思路:
本题首先得了解什么是回文结构,回文结构就是正着读反着读都一样的链表
①快慢指针法找中间节点
②后半段链表反转
③判断两端链表是否相同
④注意考虑链表为偶数的情况public boolean isPalindrome(ListNode head) { ListNode fast = head; ListNode latter = head; //找中间点 while(fast!=null&&fast.next!=null){//经典的快慢指针法找中间点,就不多bb了 fast=fast.next.next; latter=latter.next; } //后半段反转 ListNode cur=latter.next; while(cur!=null){//经典的反转链表,也不多BB了,具体方法请看第一题 ListNode curNext=cur.next;//设置暂存点 cur.next=latter; latter=cur; cur = curNext; } //判断两段链表是否相同 while(head!=latter){//head从头往后走,latter从后往前走,直到相遇 if(head.val==latter.val){//判断两段链表值是否相等 if (head.next == latter) {//考虑链表为偶数的情况 return true;//偶数链表的情况头结点下一个节点就是latter的时候直接返回true } } else{ return false; } latter=latter.next;//latter依次遍历 head=head.next;//head依次遍历 } return true;//能跳出循环说明,链表符合回文结构,返回true }
题目:
解题思路:这里说一种很6P的解法,是leetcode上看到的一个题解
直接将两条路分别拼接在对方末尾,这样两条路便一样长,再从这两条新的路起始点往后比较即可,如下图 节点相同地方一句圈起来,两条链表记住,公共节点指的就是公用一个节点,不是值相同,所以要对比的是地址,蓝色连接代表链表结束换路
①设置两个临时节点节点,分别指向A链表头结点和B链表头结点
②只要这两个临时节点不指向同一个地址,就说明还没走到第一个公共节点
③当临时节点走到一条链表的尾节点时(p1/p2.nextnull)就走另外一条链
④啥时候p1等于p2了,即p1和p2指向同一个地址了==,这个地址就是第一个公共节点的地址,返回其即可public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p1 = headA, p2 = headB;//设置两个临时节点节点 //分别指向A链表头结点和B链表头结点 while(p1 != p2){ p1 = p1 == null ? headB : p1.next;//p1依次往后遍历,走到尾节点了就走另一条链表 p2 = p2 == null ? headA : p2.next;//p2依次往后遍历,走到尾节点了就走另一条链表 } return p1;//跳出循环了说明找到公共节点了 }
题目:
解题思路:
找环其实就是一个追击问题,依旧采取双指针的方法,设置一个快指针一个慢指针,快指针每次走两步,慢指针每次走一步,如果链表有环,快指针和慢指针终究会相遇,因为跑的快的人最终肯定会超跑得慢的人一圈,当他们相遇的时候刚好超了一圈
①设置一个快指针,一个慢指针
②两个指针都指向头结点
③快指针每次走两步,慢指针每次走一步
④如果有环,两个指针一定会在某一时刻相遇,否则无环public boolean hasCycle(ListNode head) { ListNode fast = head;//设置快指针,指向头结点 ListNode slow = head;//设置慢指针,指向头结点 ListNode cur = head;//设置临时变量代替头结点,用于遍历链表 while(fast!=null&&fast.next!=null ){ fast=fast.next.next;//快指针每次走两步 slow=slow.next;//慢指针每次走一步 if(fast==slow)//快慢指针相遇 return true;//说明有环 } return false;//快慢指针没相遇说明无环 }
题目:
解题思路:
我们使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇
如下图所示,设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b 的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc
根据题意,任意时刻,fast 指针走过的距离都为slow 指针的 2 倍。因此,我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n-1)(b+c)的等量关系,我们会发现:从相遇点到入环点的距离加上 n-1圈的环长,恰好等于从链表头部到入环点的距离。
因此,当发现 slow 与 fast 相遇时,我们再额外使用一个指针 tmp它指向链表头部;随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。
解题步骤:
①利用快慢指针方法找相遇点
②找到相遇点之后,设置临时变量tmp代替头结点,tmp和slow同时移动,直至相遇
③相遇点即为环的呃入口public ListNode detectCycle(ListNode head) { if(head==null||head.next==null)//先判断链表不为空或者链表有至少两个元素 return null; //利用快慢指针,找到快慢指针的相遇点 ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast = fast.next.next; slow = slow.next; if (fast==slow){ break; } } //找到相遇点后,用临时变量代替头结点 if (fast==slow){ ListNode tmp = head;//临时变量代替头结点 while(tmp!=slow){//tmp和slow同时移动 slow = slow.next; tmp = tmp.next; } return tmp;//tmp和slow相遇的节点就是环的入口点 } return null; }
?????????????????????????
❤原创不易,如有错误,欢迎评论区留言指出,感激不尽❤
❤ 如果觉得内容不错,给个三连不过分吧~ ❤
❤ 看到会回访~ ❤
??????????????????????
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123147.html
摘要:新链表是通过拼接给定的两个链表的所有节点组成的。保证链表长度小于等于。注意,函数返回结果后,链表必须保持其原始结构。注意不作为参数进行传递,仅仅是为了标识链表的实际情况。如果是,则在该链表中没有环。说明不允许修改给定的链表。 ...
摘要:前言本章将分享十一道来自牛客网中的经典链表算法题来介绍数据结构中链表在算法题中的应用。注意,函数返回结果后,链表必须保持其原始结构。 前言:本章将分享十一道来自Le...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
摘要:此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
摘要:哪吒社区技能树打卡打卡贴函数式接口简介领域优质创作者哪吒公众号作者架构师奋斗者扫描主页左侧二维码,加入群聊,一起学习一起进步欢迎点赞收藏留言前情提要无意间听到领导们的谈话,现在公司的现状是码农太多,但能独立带队的人太少,简而言之,不缺干 ? 哪吒社区Java技能树打卡 【打卡贴 day2...
阅读 1293·2023-04-26 00:20
阅读 473·2023-04-25 21:49
阅读 3665·2021-11-12 10:35
阅读 2384·2021-09-28 09:35
阅读 627·2021-09-22 15:52
阅读 436·2021-09-07 10:16
阅读 836·2021-08-18 10:22
阅读 2554·2019-08-30 14:07