吉林省建设工程信息网站,绍兴建设网站制作,软件开发平台协议,益阳注册公司目录 一. ArrayList 与 LinkedList 的优缺点#xff1a;
二. LinkedList 的分类 三.链表的十道面试题#xff1a; 1. 删除链表中等于给定值 val 的所有节点。题目链接 2. 反转⼀个单链表。题目链接 3. 输⼊⼀个链表#xff0c;输出该链表中倒数第k个结点。题目链接 4.给定…目录 一. ArrayList 与 LinkedList 的优缺点
二. LinkedList 的分类 三.链表的十道面试题 1. 删除链表中等于给定值 val 的所有节点。题目链接 2. 反转⼀个单链表。题目链接 3. 输⼊⼀个链表输出该链表中倒数第k个结点。题目链接 4.给定⼀个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。题目链接 5.将两个有序链表合并为⼀个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。题目链接 6.编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前。题目链接 7.链表的回文结构。题目链接 8.输⼊两个链表找出它们的第一个公共结点。题目链接 9.给定⼀个链表判断链表中是否有环。题目链接 10.给定⼀个链表返回链表开始入环的第⼀个节点。如果链表无环则返回 NULL 。题目链接 四. 模拟实现 LinkedList 的一些方法。 具体什么是 “反C” 方法看图 五. LindedList 的构造 六. LinkedList 常用方法 一. ArrayList 与 LinkedList 的优缺点 ArrayList 在任意位置删除或插入元素时就需要把后面的所有元素整体往前或者往后移动时间复杂度为O(n)效率较低但是适合需要频繁访问元素的情况。空间不够会涉及到自动扩容容易浪费空间。 LinkedList 链表 可以理解为 一个长长的火车每一个 车厢 为一个对象元素也叫做节点每一个对象元素有两个或三个变量两个变量的是 单向链表三个变量的是双向链表其中链表其中一个变量一般是存放数据其余的变量存放的是其他对象的引用可以通过这个对象引用访问其他 车厢也就是节点。 LinkedList 适合 需要频繁修改节点数据时使用。 另外ArrayList 和 LinkedList 在内存存储上也有不同。ArrayList 它在内存中存储是连续的而 LinkedList 存储逻辑是连续的但是在内存不一定连续因为 LinkedList 可以通过 其节点其中的变量 来找到 下一个 节点。 二. LinkedList 的分类 LinkedList 分为一下几种结构 1.单向 或者 双向 。 2.带头 或者 不带头。 3.循环 或者 非循环。 其中 一 一 组合一共有八种结构但是我们只需要掌握两种结构就行了 1. 无头单向非循环链表 这种一般在面试笔试出现会比较多。 结构如图 val 代表的是存储的数据next 代表存储的是下一个节点的对象引用可以理解为下一个节点的地址可以通过 next 找到下一个节点 。 2.无头双向链表 在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 结构如图 val 代表的是存储的数据next 和 prev 分别代表存储的是 下一个节点 和上一个节点 的对象引用可以理解为下一个节点的地址可以通过 next 找到下一个节点 。也可以通过 prev 找到上一个节点。 三.链表的十道面试题 1. 删除链表中等于给定值 val 的所有节点。题目链接 题解思路 1.首先要判断传过来的链表是否为空若为空则返回 null 否则进入下一步。 2. 其次定义两个节点指向一个在前一个在后。 若后面的节点存储的值为val则要对节点重链接然后后节点往前走一步前节点不动。 如果后面的节点存储的值不为val则前节点走一步后节点走一步。 3.最后因为上述的过程 无法判断 最开始节点的 值所以再判断 最开始节点的值。 题解代码
if(head null) {return null;}ListNode cur head.next;ListNode curL head;while( cur ! null) {if(cur.val val) {curL.next cur.next;}else {curL cur;;}cur cur.next;}if(head.val val) {head head.next;}return head; 2. 反转⼀个单链表。题目链接 题解代码
if(head null) {return null;}if(head.next null) {return head;}ListNode cur head;ListNode curN head.next;head.next null;while(curN ! null) {ListNode curNN curN.next;curN.next cur;cur curN;curN curNN;}return cur; 题解思路 1.首先判断是否为空链表或者只有一个节点的链表的情况。 2.定义两个指向 cur 和 curN 一个在前一个在后再把头节点置为null 3.在循环里定义个 curNN 记录之后节点反转两个节点后 curN 所要在的地方。 注意循环里不用 cur.next ! null 作为条件是因为cur.next当前所指向的是前一个节点那么cur.next是访问前一个节点了。这也是什么要定义 curNN 的原因。 4.最后返回完成后的链表的头节点。 3. 输⼊⼀个链表输出该链表中倒数第k个结点。题目链接 题解代码
ListNode fast head;ListNode slow head;int count k-1;while(count ! 0) {fast fast.next;count--;}while(fast.next ! null) {fast fast.next;slow slow.next;}return slow.val;题解思路 1.首先定义两个指向 fast 和 slow 2.因为返回的是倒数第几个节点的值那么可以通过让fast 先走 k-1步再让slow 和 fast 一起走直到 fast 走到最后一个节点为止。那么slow 少走的几步就是 当前 的所需节点。 4.给定⼀个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。题目链接 题解代码
if(head null) {return null;}if(head.next null) {return head;}ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;题解思路 1.首先判断链表是否为空或者只有一个节点。 2.定义一个快指针一个慢指针。 3.每次循环让快指针走两步慢指针走一步当快指针遇到链表结尾当前的慢指针就是中间节点。特别要注意循环条件。 5.将两个有序链表合并为⼀个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。题目链接 题解代码 if(list1 null list2 null) {return null;}ListNode curA list1;ListNode curB list2;ListNode curN new ListNode(1);ListNode cur curN;while(curA ! null curB ! null) {if(curA.val curB.val) {cur.next curA;cur curA;curA curA.next;}else {cur.next curB;cur curB;curB curB.next;}}if(curA null) {cur.next curB;}if(curB null) {cur.next curA;}return curN.next; 题解思路 1.首先判断两个链表是否为空。 2.分别给两个不同的链表定义一个头节点curA 和 curB 再定义一个 “傀儡” 节点curN最后再定义一个 节点 cur 从 “傀儡” 节点开始cur用来帮助我们重新建立链表的大小链接。 3.比较 curA 和 curB 的大小小的节点 被作为 cur 重新建立顺序的一方再让 cur 走到 小节点的位置小节点再往后走一步直到某个链表走到尾部了。 4.最后把走到尾部的一方链接上 没走到尾部链表的curA 或者 curB 位置 。最后返回 “傀儡” 节点后一个节点作为新链表的起始位置。 6.编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于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 cur;be cur; }else {be.next cur;be cur;}}else {//第一次if(as null) {as ae cur;}else {ae.next cur;ae cur;}}cur cur.next;}if(bs null) {return as;}if(as null) {return bs;}ae.next null;be.next as;return bs; 题解思路 1.首先定义空引用 bs 和 be 作为 小于x 的节点存放处定义空引用 as 和 ae 作为 大于或等于 x 的节点存放处。 2.定义 引用 cur 遍历链表若 空引用 bs 和 be 或者 as 和 ae 第一次 接收节点那么把他们都赋值 为 第一次传过来的节点引用后续就只让 be 或者 ae 往后走。 3.遍历完成后分三种情况 一是没有小于x 的部分 节点bs 和 be 还是空引用那么直接返回 as 也就是原链表。 二是没有大于x 的部分 节点as 和 ae 还是空引用那么直接返回 bs 也就是原链表。 三是双方都有节点而要把 ae 当前的节点的next置为null 因为cur 遍历完链表的最后一个节点不知道是放在 be 还是 ae 所以要手动把 ae 的next 置为null 再将其两部分链接起来返回 bs 7.链表的回文结构。题目链接 题解代码
if(A null) {return false;} if(A.next null) {return true;}ListNode fast A;ListNode slow A;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}ListNode cur slow.next;while(cur ! null) {ListNode curN cur.next;cur.next slow;slow cur;cur curN;}while(A ! slow) {if(A.val ! slow.val) {return false;}if( A.next slow) {return true;}A A.next;slow slow.next;}return true; 题解思路 1.首先判断链表是否为空 或者 链表只有一个节点的情况。 2.大体思路是将后一半的链表反转过来再通过起始节点往后遍历 与 结尾节点往前遍历 对比val。 3.有个特殊情况就是链表节点个数如果为偶数的话就需要 A.next slow 的判断情况因为前面已经判断过这两个节点的val了是相等才能走到 A.next slow 的判断若是这种情况说明到中间了直接返回 true 8.输⼊两个链表找出它们的第一个公共结点。题目链接 题解代码
ListNode curL headA;ListNode curS headB;int pl 0;int ps 0;while(curL ! null) {pl;curL curL.next;}while(curS ! null) {ps;curS curS.next;}int len pl - ps;curL headA;curS headB;if(len 0) {len ps - pl;curL headB;curS headA;}while(len ! 0) {curL curL.next;len--;}while(curL ! curS) {curL curL.next;curS curS.next;}if(curL null) {return null;}return curS; 题解思路 1.首先我们假设 长节点是headA短节点 是headB再求出他们各自的链表长度再减去得到长度差。 2.得到的长度差如果是小于零的那么 长链表是 headB,短链表是headA 3.先让长链表走 len 布再让两个链表同时一起走那么循环到相同节点就是他们的链表的相交节点还要通过 curL null 判断有没有相交如果没相交返回null 。 9.给定⼀个链表判断链表中是否有环。题目链接 题解代码 ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(fast slow) {return true;}}return false;题解思路 1. 先定义一个快指针一个慢指针。 2.每次循环快指针走两步慢指针走一步。 3.每次循环判断一次 两个引用是否相等如果相等说明链表存在环若循环结束了 说明fast 走到链表尾部 该链表没有形成环。 10.给定⼀个链表返回链表开始入环的第⼀个节点。如果链表无环则返回 NULL 。题目链接 题解代码 ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(fast slow) {while(head ! slow) {head head.next;slow slow.next;}return slow;}}return null; 题解思路 1. 先定义一个快指针一个慢指针。 2.每次循环快指针走两步慢指针走一步。 3.每次循环判断一次 两个引用是否相等如果相等说明链表存在环若循环结束了 说明fast 走到链表尾部 该链表没有形成环返回null 。 4.存在环的情况下看下图 c 代表是圆环的周长所以 head 离 入环点 等于 y 所以通过上述 head 和 slow 一起走 的代码即可找到入环点。 四. 模拟实现 LinkedList 的一些方法。 注意 在Java的中LinkedList底层实现的是双向链表。 代码实现
//任意位置插入public void addIndex(int index,int data) {int len size();if(index 0 || index size()) {throw new IndexOutOfBoundsException(双向链表index位置不合法: index);}if(index 0) {addFirst(data);return;}if(index size()) {addLast(data);return;}ListNode node new ListNode(data);ListNode cur Findindex(index);node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}//寻找插入节点的后一个节点public ListNode findindex(int index) {ListNode cur head;while(index ! 0) {cur cur.next;index--;}return cur;}//头插法public void addFirst(int data) {ListNode node new ListNode(data);if(head null) {head node;last node;}else {node.next head;head.prev node;head node;}}//尾插法public void addLast(int data) {ListNode node new ListNode(data);if(head null) {head node;last node;}else {last.next node;node.prev last;last node;}} 注意 prev 是指向前一个节点next 是指向下一个节点。 代码分析 这里我们实现了头插法尾插法任意下标插入的方法。 1.头插法 首先定义一个要插入的新节点 node 再判断当前是不是空链表如果是空链表说明此时要插入的是第一个元素如果不是空链表再通过先绑定后面再绑定前面的操作进行插入元素。 2.尾插法 首先定义一个要插入的新节点 node 再判断当前是不是空链表如果是空链表说明此时要插入的是第一个元素如果不是空链表再通过先绑定后面再绑定前面的操作进行插入元素。 3.任意下标插入法 首先要判断准备要插入的下标是否合法通过 size方法得到链表的节点个数如果下标不合法就抛出个异常。 其次如果下标是 0 或者 是 size证明是头插法或者是尾插法调用其对应的方法就行了。 最后findindex 方法找到 准备插入新节点的后一个节点再通过 “反C” 方法 绑定。 具体什么是 “反C” 方法看图 按照重新链接起来的节点序号1234代表先后顺序 因为酷似 “C”顺序像从C的底部开始往上走所以被我称作 “反C”方法。 五. LindedList 的构造 LinkedList 有两种构造方法 上面的是无参的构造方法 下面的构造方法是这样的 先看图 这样的构造方法是可行的为什么 因为 list 实现了 Collection 接口并且当前的 list 是 list2 的同类型list 是 list2 的子类也行 所以是没问题的。 但是这样就不行了 虽然 list 实现了 Collection 接口但是 String 并不是 Integer 的子类。 所以必须要满足两个条件才可以实现带参数构造LinkedList。 六. LinkedList 常用方法
