【数据结构练习题】链表与LinkedList

devtools/2024/12/26 20:00:25/

顺序表与链表LinkedList

  • 选择题
  • 链表面试题
    • 1. 删除链表中等于给定值 val 的所有节点。
    • 2. 反转一个单链表。
    • 3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
    • 4. 输入一个链表，输出该链表中倒数第k个结点。
    • 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    • 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
    • 7. 链表的回文结构。
    • 8. 输入两个链表，找出它们的第一个公共结点。
    • 9. 给定一个链表，判断链表中是否有环。
    • 10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
    • 11. 删除链表中重复的结点

选择题

1
在这里插入图片描述A错误：头插不需要遍历链表，与链表长度无关
B错误：尾插不需要遍历链表，因为有一个引用指向了尾结点，可以直接插入
C错误：删除第一个节点也不需要遍历链表
D正确：删除最后一个节点之前，先要把倒数第二个节点找到，因为最后一个节点删除之后，需要将倒数第二个节点的next置为null 故需要遍历链表
因此选择D
2
在这里插入图片描述
答案：D
解析：二叉树属于树形结构，不是线性的，队列，链表，顺序表都属于线性表
3
在这里插入图片描述
答案：D
解析：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。
4
在这里插入图片描述
在这里插入图片描述
5
在这里插入图片描述
A错误：ArrayList中的元素不一定有序，ArrayList没有要求里面的元素必须有序，可能有序也可能不有序
B正确：ArrayList中的元素可以通过下标修改
C错误：ArrayList中的元素没要求必须要唯一，可以唯一也可以重复
D错误：ArrayList中的元素是通过下标访问的，而不是通过key
故正确应该选B
6
在这里插入图片描述
A正确：ArrayList 和 LinkedList都是实现了List接口
B正确：ArrayList是动态类型顺序表，插入时当空间不足时会自动扩容
C正确：LinkedList底层是链表结构，链表不支持随机访问，如果要访问任意元素只能通过查找处理
D错误：LinkedList中插入或者删除元素，只需要修改几个引用的指向即可，不需要搬移愿意，时间复杂度O(1)。ArrayList任意位置插入和删除时才需要搬移，时间复杂度O(N)

链表面试题

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

OJ链接

java">class Solution {public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==val){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}  if(head.val==val){head=head.next;} return head;}
}

2. 反转一个单链表。

OJ链接

java">class Solution {public ListNode reverseList(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curNext=cur.next;cur.next=head;head=cur;cur=curNext;}return head;}
}

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

OJ链接
在这里插入图片描述

java">class Solution {public ListNode middleNode(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}
}

4. 输入一个链表，输出该链表中倒数第k个结点。

OJ链接
在这里插入图片描述

java">import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = Integer.parseInt(sc.next());ListNode head = new ListNode(-1);ListNode temp = head;//生成链表for (int i = 0; i < n; i++) {ListNode node = new ListNode(sc.nextInt());temp.next = node;temp = temp.next;}int k = Integer.parseInt(sc.next());//使用快慢指针if(getKthFromEnd(head.next,k) != null){System.out.println(getKthFromEnd(head.next,k).val);}else{System.out.println(0);}}}//通过快慢指针搜索public static ListNode getKthFromEnd(ListNode head,int k){if(k<=0||head==null){return null;}ListNode fast=head;ListNode slow=head;for(int i=0;i<k-1;i++){fast=fast.next;}while(fast.next!=null){fast=fast.next;slow=slow.next;}return slow;}
}
class ListNode{ListNode next;int val;ListNode(int val){this.val=val;next=null;}
}

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

OJ链接
在这里插入图片描述

java">class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead=new ListNode();ListNode tmpHead=newHead;while(list1!=null&&list2!=null){if(list1.val>list2.val){tmpHead.next=list2;list2=list2.next;}else{tmpHead.next=list1;list1=list1.next;}tmpHead = tmpHead.next;}if(list1!=null)tmpHead.next=list1;if(list2!=null)tmpHead.next=list2;return newHead.next;}
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

OJ链接
在这里插入图片描述
有个易错不容易注意到：如果ae.next!=null链表会循环 此时应该将ae.next=null
在这里插入图片描述
还要设想所有数都会大于x的可能，此时会bs==null 直接return as即可

java">import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode bs=null;ListNode be=null;ListNode as=null;ListNode ae=null;ListNode cur=pHead;while(cur!=null){if(cur.val<x){//第一次插入if(bs==null){bs=be=cur;}else{be.next=cur;be=cur;//或be=be.next;}}else{if(as==null){as=ae=cur;}else{ae.next=cur;ae=cur;//或ae=ae.next;}}cur=cur.next;}//第一个段没有数据if(bs==null)return as;be.next=as;//防止最大的数据不是最后一个if(ae!=null)ae.next=null;return bs;}
}

7. 链表的回文结构。

OJ链接
在这里插入图片描述
若偶数时 则循环到最后head.next==slow即可确定true

java">import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereListNode slow=head;ListNode fast=head;//用快慢指针确定链表中点while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}ListNode cur=slow.next;//翻转后段链表while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}while(head!=slow){if(head.val!=slow.val)return false;if(head.next==slow) //偶数 head和slow不会相遇时return true;head=head.next;slow=slow.next;}return true;}
}

8. 输入两个链表，找出它们的第一个公共结点。

OJ链接
在这里插入图片描述
在这里插入图片描述

java">/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//分别求2个链表的长度ListNode pL=headA;ListNode pS=headB;int lenA=0;int lenB=0;while(pL!=null){lenA++;pL=pL.next;}while(pS!=null){lenB++;pS=pS.next;}pL=headA;pS=headB;//保证pL指向最长的链表，pS指向最短的链表，len>0int len=lenA-lenB;if(len<0){pL=headB;pS=headA;len=lenB-lenA;}//2.让最长的链表先走差值步while(len!=0){pL=pL.next;len--;}//3.就是相遇的点while(pL!=pS){pL=pL.next;pS=pS.next;}return pL;}
}

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

OJ链接

【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

  • 为什么快指针每次走两步，慢指针走一步可以？
    假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
  • 快指针一次走3步，走4步，…n步行吗？
  • 在这里插入图片描述
java">/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head==null)return false;//可以不写ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow)return true;}return false;}
}

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

OJ链接

  • 结论
    让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
  • 证明
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
java">/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head==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==null||fast.next==null)return null;fast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;}
}

11. 删除链表中重复的结点

OJ链接在这里插入图片描述
易忽略的点：应将手动将tmpHead.next置空防止后边到最后一个节点都是重复节点
在这里插入图片描述

java">import java.util.*;
/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode deleteDuplication(ListNode pHead) {ListNode cur=pHead;ListNode newHead=new ListNode(-1);ListNode tmpHead=newHead;//遍历每一个节点while(cur!=null){if(cur.next!=null&&cur.val==cur.next.val){//一直让cur走到不重复的节点 while(cur.next!=null&&cur.val==cur.next.val){cur=cur.next;}                    cur=cur.next;}else{//把这个节点加入到不重复链表中tmpHead.next=cur;tmpHead=tmpHead.next;cur=cur.next;}}//手动将tmpHead.next置空防止后边到最后一个节点都是重复节点 tmpHead.next=null;return newHead.next;}
}

http://www.ppmy.cn/devtools/145605.html

相关文章

微服务——数据管理与一致性

微服务——数据管理与一致性

1、在微服务架构中&#xff0c;每个微服务都有自己的数据库&#xff0c;这种设计有什么优点和挑战&#xff1f; 优点挑战服务自治&#xff1a;每个微服务可独立选择适合自己的数据库类型。数据一致性&#xff1a;跨微服务的事务难以保证强一致性。故障隔离&#xff1a;一个微服…
阅读更多...
ip归属地跨省会变吗？ip地址归属地不对怎么办

ip归属地跨省会变吗？ip地址归属地不对怎么办

在数字化时代&#xff0c;IP地址作为连接互联网的桥梁&#xff0c;不仅承载着数据传输的重任&#xff0c;还常常与用户的地理位置紧密相连。随着人们跨地域活动的增多&#xff0c;IP归属地的变化成为了一个普遍关注的话题。本文将深入探讨IP归属地跨省是否会发生变化&#xff0…
阅读更多...
Spring源码_05_IOC容器启动细节

Spring源码_05_IOC容器启动细节

前面几章&#xff0c;大致讲了Spring的IOC容器的大致过程和原理&#xff0c;以及重要的容器和beanFactory的继承关系&#xff0c;为后续这些细节挖掘提供一点理解基础。掌握总体脉络是必要的&#xff0c;接下来的每一章都是从总体脉络中&#xff0c; 去研究之前没看的一些重要…
阅读更多...
微软在AI时代的战略布局和挑战

微软在AI时代的战略布局和挑战

微软的CEO萨提亚纳德拉&#xff08;Satya Nadella&#xff09;在与投资人比尔格里&#xff08;Bill Gurley&#xff09;和布拉德格斯特纳&#xff08;Brad Gerstner&#xff09;的一场深度对话中&#xff0c;详细回顾了微软在AI时代的战略布局与所面临的挑战。这场对话不仅总结…
阅读更多...
记录学习《手动学习深度学习》这本书的笔记（六）

记录学习《手动学习深度学习》这本书的笔记（六）

看到第九章&#xff1a;现代循环神经网络了&#xff0c;循环神经网络这块真的有点难&#xff0c;而且老师也没有细讲这块&#xff0c;只能自己慢慢理解。 第九章&#xff1a;现代循环神经网络 9.1 门控循环单元&#xff08;GRU&#xff09; 这一节介绍了一个循环神经网络的“…
阅读更多...
【报错】node:internal/modules/cjs/loader:936

【报错】node:internal/modules/cjs/loader:936

报错问题&#xff1a; 当执行npm run dev后&#xff0c;出现下面错误 这个错误一般是由于Node.js无法找到所需的模块而引起的&#xff0c;解决此问题的一种方法就是重新安装所需的模块。 解决办法&#xff1a; 删除npm install 所下载在项目里的node_modules文件执行操作&…
阅读更多...
LightGBM分类算法在医疗数据挖掘中的深度探索与应用创新(上)

LightGBM分类算法在医疗数据挖掘中的深度探索与应用创新(上)

一、引言 1.1 医疗数据挖掘的重要性与挑战 在当今数字化医疗时代，医疗数据呈爆炸式增长，这些数据蕴含着丰富的信息，对医疗决策具有极为重要的意义。通过对医疗数据的深入挖掘，可以发现潜在的疾病模式、治疗效果关联以及患者的健康风险因素，从而为精准医疗、个性化治疗方…
阅读更多...
设计模式详解（建造者模式）

设计模式详解（建造者模式）

1、简述 建造者模式&#xff08;Builder Pattern&#xff09;是一种创建型设计模式&#xff0c;它通过将对象的构造过程与表示分离&#xff0c;使得相同的构造过程可以创建不同的表示。建造者模式尤其适用于创建复杂对象的场景。 2、什么是建造者模式&#xff1f; 建造者模式…
阅读更多...
最新文章

Copyright @ 2022~2023