曹县网站建设,无锡 电子商务网站建设,什么类型的网站容易做,wordpress畅言评论使用教程目录
前言
1、删除链表中等于给定值val的所有节点。
【题目描述】
【代码示例】
【 画图理解】 2、反转一个点链表
【题目描述】
【 代码思路】 【代码示例】 【画图理解】
3、给定一个带有头节点head的非空单链表#xff0c;返回链表的中间节点#xff0c;如果有两个…目录
前言
1、删除链表中等于给定值val的所有节点。
【题目描述】
【代码示例】
【 画图理解】 2、反转一个点链表
【题目描述】
【 代码思路】 【代码示例】 【画图理解】
3、给定一个带有头节点head的非空单链表返回链表的中间节点如果有两个中间节点则返回第二个中间节点。
❗❗❗【快慢指针】
【代码示例】 【画图理解】 4、输入一个链表输出该链表中倒数第k个节点
【题目描述】
【快慢指针】
5、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
【题目描述】
【代码示例】 【画图理解】 6、链表的回文结构
【题目描述】
【代码示例】
【画图解释】
7、编写代码以给定值x为基准将链表分割成两部分所有小于x的节点排在大于或等于x的节点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。
【最终效果】 【代码思路】 【代码示例】
8、链表相交
【题目描述】 【代码思路】
【代码示例】
9、给定一个链表判断链表中是否有环
【题目描述】
【解题思路】
❓❓❓【问题拓展】
【代码示例】
10、给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回NULL。
【问题描述】 【代码思路】 【代码示例】 前言 这些练习题中让返回头节点的题目在测试方法的时候使用上一个博客当中的display方法进行输出。 1、删除链表中等于给定值val的所有节点。
【题目描述】 【代码示例】 【 画图理解】 2、反转一个点链表
【题目描述】 ❌❌❌这里很多人会想到将链表当中的数值放到数组当中将数组逆置这种思路是掩耳盗铃我们要的是将链表本身逆置一下而不是将链表当中的数据进行反转。 ❗❗❗这里我们要求这个方法的时间复杂度为O(1)。 【 代码思路】 先将头节点head的地址域置为null再使用cur变量来遍历链表的节点将遍历到的cur节点使用头插法放在head的前面。再使用curNext记录cur节点的下一个节点方便将节点插入到前面之后回来继续遍历剩下的链表cur来到curNext的位置。【代码示例】 【画图理解】 3、给定一个带有头节点head的非空单链表返回链表的中间节点如果有两个中间节点则返回第二个中间节点。
❗❗❗【快慢指针】 此题使用快慢指针定义两 个指针一个fast指针一个slow指针。fast指针和slow指针是同时出发的fast指针走两步slow指针走一步。fast是slow的两倍当fast指针走到链表的结尾时slow指针走到链表的中间。 【代码示例】 【画图理解】 ❗❗❗注意 ❓❓❓循环的判断条件fast ! null和fast.next ! null是否可以调换位置为什么 ✨答案是不行 当两个条件交换位置fast将链表循环完成之后fastnull时执行fast.next ! null时会报空指针异常 。如果不交换位置fastnull时程序就不会进入while循环不会通过fast ! null条件。也就不会报空指针异常4、输入一个链表输出该链表中倒数第k个节点
【题目描述】 要求只遍历一遍链表
【快慢指针】 此题使用快慢指针来解定义两个指针fast和slow。 ❗❗ 也可以fast和slow相差k步只不过fastnull若相差k-1步fast.next null. 【代码思路】 先让fast走k-1步fast走完之后fast和slow开始一步一步走当fast.next为空的时候slow所指向的位置就是倒数第k个节点/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if(k0 || head null){//判断k的合法性当链表为空时fast和slow都为空这是就会报空指针异常所以要将这个情况去除掉return null;}ListNode fast head;ListNode slow head;//定义快慢指针//fast走k-1步while(k-1 ! 0){fast fast.next;//fast指针向后移动
//理论条件下k若合法那就不用这句代码判断但是当ksize()时fast通过向后移动就会造成空指针异常。if(fast null){//但是写了这个判断在测试这个类当ksize()时编译器还是会报错这是正常情况。这里已经将这种情况去除掉了return null;}k--;}while(fast.next ! null){//判断条件fast走到最后一个节点结束循环。若在向后走fast就为空了。fast fast.next;slow slow.next;}return slow;}
}5、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
【题目描述】 【代码示例】
/*** 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 head1, ListNode head2) {ListNode NewHead new ListNode(0);//创建一个虚拟节点给其数值为0他不动作为新链表的头节点ListNode tmp NewHead;//用tmp变量来接收虚拟链表while(head1 ! null head2 ! null){//循环条件是两个链表都不为空if(head1.valhead2.val){//如果head1的值大于head2的值tmp.next head1;//tmp节点指向head1节点head1 head1.next;//head1节点向后移动进行第二次比较tmp tmp.next;//tmp向后移动将较小值的节点的地址传给tmp节点}else{tmp.next head2;//head2的值大于head1的值将head2的地址传给tmphead2 head2.next;//head2向后移动进行第二次比较tmp tmp.next;//tmp向后移动将较小值的节点的地址传给tmp节点}}if(head1 null){//当head1链表遍历完head2链表还没有遍历完tmp直接指向head2剩余节点。tmp.next head2;}if(head2 null){tmp.next head1;}return NewHead.next;//因为NewHead作为虚拟节点在新链表产生之后输出的时候不需要头节点NewHead的值从第二个节点开始输出。所以返回NewHead下一个节点}
} 【画图理解】 6、链表的回文结构
【题目描述】 【代码示例】
/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {if(head null){//为空链表的情况return false;}if(head.next null){//只有一个节点的情况return true;}ListNode fast head;ListNode slow head;//找中间节点while(fast ! null fast.next ! null){//两个判断条件的原因时fast指针不能为空因为fast定义的时候被赋值为head若fast为空则代码报空指针异常两个判断条件也不能调换顺序fast fast.next.next;slow slow.next;}//翻转ListNode cur slow.next;//cur代表当前需要反转的节点while(cur ! null){ListNode curNext cur.next;//curNext作为标记cur节点反转之后就不会指向cur原本后面的节点所以用curNext记录.cur.next slow;slow cur;//slow指针向后走cur curNext;//cur也向后走}//一个从前往后一个从后往前while(slow ! head){//slow和head走到同一个节点相遇循环结束if(head.val ! slow.val){//在循环期间head.val ! slow.val,结束这个链表不是循环链表return false;}
//当链表的节点数为偶数的时候用此if来判断时偶数节点的情况if(head.next slow){//当存在链表节点数为偶数的情况head和slow不可能同时走到一个节点上当两个相邻时该链表为回文链表。return true;}slow slow.next;//若两个值相等则slow往前head head.next;//head向后}return true;}
}
【画图解释】 7、编写代码以给定值x为基准将链表分割成两部分所有小于x的节点排在大于或等于x的节点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。
【最终效果】 【代码思路】 在链接连个部分的内容时还分两种情况 x部分没有内容直接返回x部分的内容。x部分不为空并且x部分不为空将两个内容连接起来 并将连接起来的链表的最后一个节点的next置为null.【代码示例】
public class LinkedLast {class Node{public int val;public Node next;public Node(int val){this.val val;}}public Node head;public Node partition(int x){Node bs null;Node be null;Node as null;Node ae null;Node cur head;while(cur ! null){//cur又来遍历链表当cur将链表遍历完循环结束if(cur.val x){//cur遍历到的节点的值小于xif(bs null){//判断是不是第一次插入如bs cur;//是第一次插入bs和be同时指向cur指向节点be cur;}else{be.next cur;//be用来记录新遍历到的地址将两个节点串起来be be.next;//be用来记录结尾所以向后移动到最新遍历到的节点上}}else{//若cur遍历到x的节点if(as null){//判断是不是不第一次插入as cur;ae cur;}else{ae.next cur;//ae用来记录新遍历到的地址将两个节点串起来ae ae.next;//ae用来记录结尾所以向后移动到最新遍历到的节点上}}cur cur.next;//cur遍历链表}//有可能x的部分有节点x部分没节点也有可能结果相反if(bs null){//如果第一个里面没有节点那就返回第二个部分return as;//如果两个都为空那么返回的是null,因为as初始赋值为null.}//第一个部位不为空be.next as;//将两个部分串起来若as为空那就表示只有一个部分if(as ! null){//如果第二个部分不为空进入将链表的最后一个节点的next置为nullae.next null;}return bs;//返回新链表的头节点}
}8、链表相交
【题目描述】 【代码思路】 当然上图考虑的情况还不全 当两个链表都为空的情况那么就返回null,当两个链表当中有一个为空的情况返回null.【代码示例】 ❗❗❗主要流程 定义pl和ps两个指针用来遍历两个链表headA和headB.计算两个链表的长度求链表长度的差值len。当遍历完链表之后让pl和ps指针从链表的结尾返回到开头让pl指向较长链表并且先走len步之后让ps和pl同步前进pl和ps指向两个链表的相交节点返回pl1、创建的链表类
public class LinkedLast {class Node{public int val;public Node next;public Node(int val){this.val val;}}public Node head;
}
2、 由于题目中要求的是两个链表所以在测试类当中来写这个方法通过类来创建两个链表
public class Test { public static LinkedLast.Node getIntersectionNode(LinkedLast.Node headA, LinkedLast.Node headB) {//1、分别求两个链表的长度int lenA 0;int lenB 0;LinkedLast.Node pl headA;//pl指向的链表是长链表LinkedLast.Node ps headB;//ps指向的链表是短链表while(pl ! null){lenA;//遍历从第一个节点开始所以要先再向后移动。pl pl.next;}while(ps ! null){lenB;ps ps.next;}//2、通过上述计算链表的长度pl和ps都指向了链表的结尾通过下面的操作让他们再指向链表的开头。pl headA;ps headB;int len lenA - lenB;//大小//3、根据len的值修改指向//下面这个if判断可以保证1、len一定是一个正数 2、pl指向的链表一定是最长的ps指向的链表一定是最短的if(len 0){//表示lenA的长度小于lenB的长度pl headB;//交换指向headB长pl指向headBps headA;//headA较短ps指向headAlen lenB-lenA;}//pl走差值部分while(len ! 0){//当两个链表长度存在差值时较长链表先走pl pl.next;len--;}while(pl ! ps){//pl和ps没有指向同一个节点那么继续向后遍历直到相交pl pl.next;ps ps.next;}//当上面的程序运行完pl一定等于ps即使两个链表当中有一个链表为空当较长的链表遍历完之后plnull,所以plpsif(pl ps pl null){//当两个链表当中有一个为空那么输出nullreturn null;}return pl;//否则返回pl}
}来测试一下这个方法
public class Test {public static void main(String[] args) {LinkedLast linkedLast new LinkedLast();LinkedLast linkedLast1 new LinkedLast();linkedLast.addFirst(21);//头插法插入的数据顺序与链表输出的数据相反linkedLast.addFirst(23);linkedLast.addFirst(78);linkedLast.addFirst(96);linkedLast1.addFirst(12);linkedLast1.addFirst(15);linkedLast1.addFirst(14);linkedLast1.addFirst(11);createCut(linkedLast.head,linkedLast1.head);LinkedLast.Node ret getIntersectionNode(linkedLast.head,linkedLast1.head);System.out.println(ret.val);}
//这个方法让两个链表相交public static void createCut(LinkedLast.Node headA,LinkedLast.Node headB){headB.next.next headA.next.next;} 9、给定一个链表判断链表中是否有环
【题目描述】 【解题思路】 使用快慢指针来解这个问题让快指针先走两步慢指针走一步最后两个指针若能相遇则链表当中有环。 ❓❓❓【问题拓展】
1、为什么要设置快指针每次走两步慢指针走一步 假设链表带环两个指针最后会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的举例刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好套圈的情况因此在慢指针走到一圈之前快指针坑定是可以追上慢指针的即相遇。 2、快指针一次走3步走4步....n步慢指针走一步可以吗 假设快指针每次走3步慢指针每次走一步此时快指针肯定先进环慢指针后来才进环。假设慢指针进环时候快指针的位置如图所示 此时按照上述方法来绕环移动每次快指针走3步慢指针走1步是永远不会相遇的快指针刚好将慢指针套圈了因此不行。只有快指针走2步慢指针走1步才可以因为环的最小长度是1即使套圈了快指针也只是将慢指针套了一次两个也在相同的位置。【代码示例】
第一种写法
public class LinkedLast {class Node{public int val;public Node next;public Node(int val){this.val val;}}public Node head;public boolean hasCycle() {Node fast head;Node slow head;while (fast ! null fast.next ! null) {//不论链表的节点是单数还是双数都要有环fast null和fast.next null表示将链表循环结束fast fast.next.next;slow slow.next;if (fast slow) {//判断两个指针相遇则返回true不相遇返回falsereturn true;}}return false;}
第二种写法
public class LinkedLast {class Node{public int val;public Node next;public Node(int val){this.val val;}}public Node head;public boolean hasCycle() {Node fast head;Node slow head;while (fast ! null fast.next ! null) {//循环的判断条件是不论链表的节点是单数还是双数都要有环fast null和fast.next null表示将链表循环结束fast fast.next.next;slow slow.next;if (fast slow) {//判断两个指针相遇则返回true不相遇返回falsebreak;}}if(fast null || fast.next null){//将链表循环完没有进入环说明链表没有环return false;}return true;} 10、给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回NULL。
【问题描述】 【代码思路】 【代码示例】 public class LinkedLast {class Node{public int val;public Node next;public Node(int val){this.val val;}}public Node head;public LinkedLast.Node detectCycle(){Node fast head;Node slow head;//1、找相遇点while (fast ! null fast.next ! null) {//循环的判断条件是不论链表的节点是单数还是双数都要有环fast null和fast.next null表示将链表循环结束fast fast.next.next;slow slow.next;if (fast slow) {//判断两个指针相遇则返回true不相遇返回falsebreak;}}if(fast null || fast.next null){//将链表循环完没有进入环说明链表没有环return null;}//链表若是有环将上述代码走完两个指针相遇。找到相遇点slow head;//slow回到链表的开头//2、找入口点while(fast ! slow){//当两个指针没有再次相遇时fast fast.next;//fast和slow以相同的速度向前挪动直到再次相遇找到入环的第一个节点slow slow.next;}return fast;}
}
