当前位置： 首页 > news >正文

【数据结构】单向链表的练习题

news 2025/6/27 17:50:43

目录

前言

1、删除链表中等于给定值val的所有节点。

【题目描述】

【代码示例】

【 画图理解】

 2、反转一个点链表

【题目描述】

【 代码思路】

 【代码示例】

 【画图理解】

3、给定一个带有头节点head的非空单链表，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点。

❗❗❗【快慢指针】

【代码示例】 

 【画图理解】

 4、输入一个链表，输出该链表中倒数第k个节点

【题目描述】

【快慢指针】

5、将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

【题目描述】

【代码示例】

 【画图理解】

 6、链表的回文结构

【题目描述】

【代码示例】 

【画图解释】 

7、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的节点排在大于或等于x的节点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

【最终效果】

 【代码思路】

 【代码示例】

8、链表相交

【题目描述】

 【代码思路】

【代码示例】 

9、给定一个链表，判断链表中是否有环

【题目描述】

【解题思路】

❓❓❓【问题拓展】

【代码示例】 

10、给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回NULL。

【问题描述】

 【代码思路】

 【代码示例】

前言

这些练习题中，让返回头节点的题目，在测试方法的时候，使用上一个博客当中的display方法进行输出。

1、删除链表中等于给定值val的所有节点。

【题目描述】

【代码示例】

【 画图理解】


 2、反转一个点链表

【题目描述】

 

 ❌❌❌这里很多人会想到将，链表当中的数值放到数组当中，将数组逆置，这种思路是掩耳盗铃，我们要的是将链表本身逆置一下，而不是将链表当中的数据进行反转。

❗❗❗这里我们要求这个方法的时间复杂度为O(1)。

【 代码思路】

  1. 先将头节点head的地址域置为null；
  2. 再使用cur变量来遍历链表的节点，将遍历到的cur节点使用头插法放在head的前面。
  3. 再使用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.

【代码思路】

  1. 先让fast走k-1步
  2. fast走完之后，fast和slow开始一步一步走
  3. 当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的节点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

【最终效果】


 【代码思路】

在链接连个部分的内容时，还分两种情况

  1. <x部分没有内容，直接返回>=x部分的内容。
  2. <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.

【代码示例】 

❗❗❗主要流程

  1. 定义pl和ps两个指针，用来遍历两个链表headA和headB.
  2. 计算两个链表的长度，求链表长度的差值len。
  3. 当遍历完链表之后，让pl和ps指针从链表的结尾返回到开头
  4. 让pl指向较长链表，并且先走len步，之后让ps和pl同步前进
  5. 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;}
}

http://www.lryc.cn/news/2286.html

相关文章：

  • 我的企业需要一个网站吗？答案是肯定的 10 个理由
  • CHI协议定义的NOC组件
  • Python+Flask+MySQL开发的在线外卖订餐系统（附源码）
  • OpenStack云平台搭建(4) | 部署Placement
  • GNN图神经网络原理解析
  • BI-SQL丨ALL、ANY、SOME
  • 从0到0.1学习 maven(三：声明周期、插件、聚合与继承)
  • 【直击招聘C++】2.5 this指针
  • spark数据清洗练习
  • Android 12首次开机启动Launcher前黑屏问题解析
  • 使用 LSSVM 的 Matlab 演示求解反常微分方程问题（Matlab代码实现）
  • 动态规划-背包问题
  • 计算24点与运算符重载
  • MES系统智能工厂,搭上中国制造2025顺风车
  • 【LeetCode】每日一题（1）
  • SpringCloud-Netflix学习笔记11——Hystrix实现服务降级
  • Oracle Dataguard（主库为 Oracle rac 集群）配置教程（03）—— 创建 dataguard 数据库之前的准备工作
  • 零代码做分析报表的bi软件才是好软件
  • linux ALSA 驱动架构
  • JDK 8 JVM内存结构详解
  • 黑马程序员 Linux 教程
  • 文件操作 -- IO
  • FPGA解析串口协议帧3.0版本，增加了错误重发功能，提供仿真文件以及源码
  • 365天深度学习训练营 第P6周：好莱坞明星识别
  • 一文读懂 Zebec Chain 的“先行网络” Nautilus 链
  • FuzzyMathematicalModel模糊数学模型-2-多目标模糊综合评价案例分享
  • 单链表--C语言版（从0开始，超详细解析，小白一看就会）
  • cv2-特征点匹配（bf、FLANN）
  • 基于matlab多功能相控阵雷达资源管理的服务质量优化
  • 立创eda专业版学习笔记（6）（pcb板移动节点）