来广营网站建设百度手机卫士下载安装
目录
前言
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将链表循环完成之后，fast=null时，执行fast.next != null时，会报空指针异常 。
- 如果不交换位置，fast=null时，程序就不会进入while循环，不会通过fast != null条件。也就不会报空指针异常
4、输入一个链表，输出该链表中倒数第k个节点
【题目描述】
要求：只遍历一遍链表
【快慢指针】
此题使用快慢指针来解，定义两个指针，fast和slow。
❗❗ 也可以fast和slow相差k步，只不过fast=null；若相差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(k<=0 || 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若合法，那就不用这句代码判断，但是当k>size()时，fast通过向后移动就会造成空指针异常。if(fast == null){//但是写了这个判断，在测试这个类当k>size()时，编译器还是会报错，这是正常情况。这里已经将这种情况去除掉了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.val<head2.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指向两个链表的相交节点，返回pl
1、创建的链表类
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，即使两个链表当中有一个链表为空，当较长的链表遍历完之后，pl==null,所以pl==psif(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;}
}