网站建设领域文章,php 企业 网站,长沙网站制作的,玉溪市建设局网站本篇文章主要讲述LinkedList链表中从初识到深入相关总结#xff0c;常见OJ题秒AC#xff0c;望各位大佬喜欢 一、单链表
1.1链表的概念及结构
1.2无头单向非循环链表模拟实现
1.3测试模拟代码 1.4链表相关面试OJ题
1.4.1 删除链表中等于给定值 val 的所有节点
1.4.2 反转…本篇文章主要讲述LinkedList链表中从初识到深入相关总结常见OJ题秒AC望各位大佬喜欢 一、单链表
1.1链表的概念及结构
1.2无头单向非循环链表模拟实现
1.3测试模拟代码 1.4链表相关面试OJ题
1.4.1 删除链表中等于给定值 val 的所有节点
1.4.2 反转一个单链表
1.4.3 给你单链表的头结点 head 请你找出并返回链表的中间结点
1.4.4 输入一个链表输出该链表中倒数第k个结点
1.4.5 合并俩个有序链表
二、双链表
2.1双向链表模拟实现
2.2LinkedList其他常用方法介绍
2.3ArrayList和LinkedList的区别 1.1链表的概念及结构 由于顺序表ArrayList不适合从任意位置插入或者删除元素因此引入了LinkedList链表链表是一种物理存储结构上非连续存储结构也称链式存储数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 实际中链表的结构非常多样以下情况组合起来就有8种链表结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 4.无头单向非循环链表或者无头双向链表 在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 1.2无头单向非循环链表模拟实现
public class MySingleList {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;public void createLink() {ListNode node1 new ListNode(12);ListNode node2 new ListNode(13);ListNode node3 new ListNode(14);ListNode node4 new ListNode(16);node1.next node2;node2.next node3;node3.next node4;head node1;}/*** author 徐延焜xyk* Description//遍历链表*/public void display() {ListNode cur head;while (cur ! null) {System.out.println(cur.val );cur cur.next;}System.out.println();}/*** author 徐延焜xyk* Description//查找是否包含关键字key是否在单链表当中*/public boolean contains(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {return true;}cur cur.next;}return false;}/*** author 徐延焜xyk* Description//得到单链表的长度 O(N)*/public int size() {int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}/*** author 徐延焜xyk* Description//头插法 O(1)*/public void addFirst(int data) {ListNode node new ListNode(data);node.next head;head node;}/*** author 徐延焜xyk* Description//尾插法 O(N) 找尾巴的过程*/public void addLast(int data) {ListNode node new ListNode(data);if (head null) {head node;return;}ListNode cur head;while (cur.next ! null) {cur cur.next;}cur.next node;}/*** author 徐延焜xyk* Description //任意位置插入,第一个数据节点为0号下标*/public void addIndex(int index, int data) throws ListIndexOutofException {checkIndex(index);if (index 0) {addFirst(data);return;}if (index size()) {addFirst(data);return;}ListNode cur findIndexSubOne(index);ListNode node new ListNode(data);node.next cur.next;cur.next node;}/*** author 徐延焜xyk* Description找到 index-1位置的节点的地址*/private ListNode findIndexSubOne(int index) {ListNode cur head;int count 0;while (count ! index - 1) {cur cur.next;count;}return cur;}private void checkIndex(int index) throws ListIndexOutofException {if (index 0 || index size()) {throw new ListIndexOutofException(index位置不合法);}}/*** author 徐延焜xyk* Description//删除第一次出现关键字为key的节点 O(N)*/public void remove(int key) {if (head null) {return;}if (head.val key) {head head.next;return;}ListNode cur searchPrev(key);if (cur null) {return;}ListNode del cur.next;cur.next del.next;}/*** author 徐延焜xyk* Description找到关键字key的前一个节点*/private ListNode searchPrev(int key) {ListNode cur head;while (cur.next ! null) {if (cur.next.val key) {return cur;}cur cur.next;}return null;}/*** author 徐延焜xyk* Description//删除所有值为key的节点*/public void removeAllKey(int key) {if (head null) {return;}ListNode prev head;ListNode cur head.next;while (cur ! null) {if (cur.val key) {prev.next cur.next;cur cur.next;} else {prev cur;cur cur.next;}if (head.val key) {head head.next;}}}/*** author 徐延焜xyk* Description保证链表当中 所有的节点 都可以被回收*/public void clear() {head null;}
}
1.3测试模拟代码
public static void main(String[] args) {MySingleList mySingleList new MySingleList();//LinkedListInteger stack new LinkedListInteger();//QueueMySingleList.ListNode queue new ArrayDeque();mySingleList.display();System.out.println();System.out.println(mySingleList.contains(90));System.out.println(mySingleList.size());System.out.println(测试插入);mySingleList.addLast(1);mySingleList.addLast(2);mySingleList.addLast(3);mySingleList.addLast(4);try {mySingleList.addIndex(0,1);}catch (ListIndexOutofException e) {e.printStackTrace();}mySingleList.display();System.out.println();mySingleList.removeAllKey(1);mySingleList.display();} 1.4链表相关面试OJ题
1.4.1 删除链表中等于给定值 val 的所有节点 1. 删除链表中等于给定值 val 的所有节点。203. 移除链表元素 - 力扣LeetCode class Solution {public ListNode removeElements(ListNode head, int val) {if (head null){return null;}ListNode prev head;ListNode cur head.next;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;}
}
1.4.2 反转一个单链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 206. 反转链表 - 力扣LeetCode 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;}
}
1.4.3 给你单链表的头结点 head 请你找出并返回链表的中间结点 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 876. 链表的中间结点 - 力扣LeetCode class Solution {public ListNode middleNode(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null){fast fast.next.next;slow slow.next;}return slow;}
}
1.4.4 输入一个链表输出该链表中倒数第k个结点 链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com) 仅仅用一个指针进行遍历注定是没有办法很优美地实现此问题解答的所以要用两个指针这两个指针的位置相差k-1个距离当快指针走到最后一个节点的时候慢指针指向的位置就是我们要的倒数第k个节点了。思想就是这么简单了很多链表类的题目都是活用指针就可以解决的一个指针不可以的时候就两个指针来完成。 public class Solution {public ListNode FindKthToTail(ListNode head, int k) {if (k 0 || head null) {return null;}ListNode fast head;ListNode slow head;while (k - 1 ! 0) {fast fast.next;if (fast null) {return null;}k--;}while (fast.next ! null) {fast fast.next;slow slow.next;}return slow;}
}1.4.5 合并俩个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 21. 合并两个有序链表 - 力扣LeetCode class Solution {public ListNode mergeTwoLists(ListNode head1, ListNode head2) {ListNode newHead new ListNode(0);ListNode tmp newHead;while (head1 ! null head2 ! null){if (head1.val head2.val){tmp.next head1;head1 head1.next;tmp tmp.next;}else {tmp.next head2;head2 head2.next;tmp tmp.next;}}if (head1 ! null){tmp.next head1;}if (head2 ! null){tmp.next head2;}return newHead.next;}
}
上述这些oj题都是最基本的题目请关注后续播客会有难度题上线
二、双链表
2.1双向链表模拟实现
public class MyLinkedList {static class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val val;}}public ListNode head;public ListNode last;//头插法O(1)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;}}//尾插法O(1)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;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data) {if (index 0 || index size()) {throw new ListIndexOutOfException();}if (index 0) {addFirst(data);return;}if (index size()) {addLast(data);return;}ListNode cur findIndex(index);ListNode node new ListNode(data);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;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {return true;}cur cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {//1. 删除的是头节点if (cur head) {head head.next;//只有一个节点if (head ! null) {head.prev null;}} else {//中间 尾巴cur.prev.next cur.next;//不是尾巴节点if (cur.next ! null) {cur.next.prev cur.prev;} else {//是尾巴节点last last.prev;}}return;}cur cur.next;}}//删除所有值为key的节点public void removeAllKey(int key) {ListNode cur head;while (cur ! null) {if (cur.val key) {//1. 删除的是头节点if (cur head) {head head.next;//只有一个节点if (head ! null) {head.prev null;}} else {//中间 尾巴cur.prev.next cur.next;//不是尾巴节点if (cur.next ! null) {cur.next.prev cur.prev;} else {//是尾巴节点last last.prev;}}}cur cur.next;}}public int size() {int len 0;ListNode cur head;while (cur ! null) {len;cur cur.next;}return len;}public void display() {ListNode cur head;while (cur ! null) {System.out.println(cur.val );cur cur.next;}System.out.println();}public void clear() {ListNode cur head;while (cur ! head) {ListNode curNext cur.next;cur.prev null;cur.next null;cur curNext;}head null;last null;}测试代码public static void main(String[] args) {MyLinkedList linkedList new MyLinkedList();linkedList.addLast(1);linkedList.display();} 1. LinkedList实现了List接口 2. LinkedList的底层使用了双向链表 3. LinkedList没有实现RandomAccess接口因此LinkedList不支持随机访问 4. LinkedList的任意位置插入和删除元素时效率比较高时间复杂度为O(1) 5. LinkedList比较适合任意位置插入的场景 2.2LinkedList其他常用方法介绍
方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标ListE subList(int fromIndex, int toIndex)截取部分 list
LinkedListInteger list new LinkedList();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list); 2.3ArrayList和LinkedList的区别
不同点ArrayListLinkedList存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)头插需要搬移元素效率低O(N)只需修改引用的指向时间复杂度为O(1)插入空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁
文章转载自： http://www.morning.jqmqf.cn.gov.cn.jqmqf.cn http://www.morning.mjmtm.cn.gov.cn.mjmtm.cn http://www.morning.rnyhx.cn.gov.cn.rnyhx.cn http://www.morning.qcymf.cn.gov.cn.qcymf.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.rwfj.cn.gov.cn.rwfj.cn http://www.morning.mnwmj.cn.gov.cn.mnwmj.cn http://www.morning.nwtmy.cn.gov.cn.nwtmy.cn http://www.morning.lsnhs.cn.gov.cn.lsnhs.cn http://www.morning.zdqsc.cn.gov.cn.zdqsc.cn http://www.morning.lxhrq.cn.gov.cn.lxhrq.cn http://www.morning.nckjk.cn.gov.cn.nckjk.cn http://www.morning.brwnd.cn.gov.cn.brwnd.cn http://www.morning.mxnhq.cn.gov.cn.mxnhq.cn http://www.morning.cqrenli.com.gov.cn.cqrenli.com http://www.morning.jhxdj.cn.gov.cn.jhxdj.cn http://www.morning.jqmmf.cn.gov.cn.jqmmf.cn http://www.morning.pbsfq.cn.gov.cn.pbsfq.cn http://www.morning.qydgk.cn.gov.cn.qydgk.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.jxmjr.cn.gov.cn.jxmjr.cn http://www.morning.etsaf.com.gov.cn.etsaf.com http://www.morning.fmrd.cn.gov.cn.fmrd.cn http://www.morning.dgwrz.cn.gov.cn.dgwrz.cn http://www.morning.rmfwh.cn.gov.cn.rmfwh.cn http://www.morning.xckrj.cn.gov.cn.xckrj.cn http://www.morning.gthc.cn.gov.cn.gthc.cn http://www.morning.fbxdp.cn.gov.cn.fbxdp.cn http://www.morning.kjxgc.cn.gov.cn.kjxgc.cn http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.hysqx.cn.gov.cn.hysqx.cn http://www.morning.zkrzb.cn.gov.cn.zkrzb.cn http://www.morning.knqck.cn.gov.cn.knqck.cn http://www.morning.lywys.cn.gov.cn.lywys.cn http://www.morning.srltq.cn.gov.cn.srltq.cn http://www.morning.pwmm.cn.gov.cn.pwmm.cn http://www.morning.ryspp.cn.gov.cn.ryspp.cn http://www.morning.dswtz.cn.gov.cn.dswtz.cn http://www.morning.ndlww.cn.gov.cn.ndlww.cn http://www.morning.wcczg.cn.gov.cn.wcczg.cn http://www.morning.nlqgb.cn.gov.cn.nlqgb.cn http://www.morning.mfxcg.cn.gov.cn.mfxcg.cn http://www.morning.dygqq.cn.gov.cn.dygqq.cn http://www.morning.dtmjn.cn.gov.cn.dtmjn.cn http://www.morning.mrskk.cn.gov.cn.mrskk.cn http://www.morning.rylr.cn.gov.cn.rylr.cn http://www.morning.ryfpx.cn.gov.cn.ryfpx.cn http://www.morning.bsrqy.cn.gov.cn.bsrqy.cn http://www.morning.ckfyp.cn.gov.cn.ckfyp.cn http://www.morning.joinyun.com.gov.cn.joinyun.com http://www.morning.dgknl.cn.gov.cn.dgknl.cn http://www.morning.jgykx.cn.gov.cn.jgykx.cn http://www.morning.jwfkk.cn.gov.cn.jwfkk.cn http://www.morning.wsnjn.cn.gov.cn.wsnjn.cn http://www.morning.nlkhr.cn.gov.cn.nlkhr.cn http://www.morning.xymkm.cn.gov.cn.xymkm.cn http://www.morning.ydrml.cn.gov.cn.ydrml.cn http://www.morning.rwwdp.cn.gov.cn.rwwdp.cn http://www.morning.yqyhr.cn.gov.cn.yqyhr.cn http://www.morning.jqrp.cn.gov.cn.jqrp.cn http://www.morning.rynq.cn.gov.cn.rynq.cn http://www.morning.rysmn.cn.gov.cn.rysmn.cn http://www.morning.wwznd.cn.gov.cn.wwznd.cn http://www.morning.lphtm.cn.gov.cn.lphtm.cn http://www.morning.gmgyt.cn.gov.cn.gmgyt.cn http://www.morning.nqrdx.cn.gov.cn.nqrdx.cn http://www.morning.rykw.cn.gov.cn.rykw.cn http://www.morning.qhrdx.cn.gov.cn.qhrdx.cn http://www.morning.qbwmz.cn.gov.cn.qbwmz.cn http://www.morning.yrfxb.cn.gov.cn.yrfxb.cn http://www.morning.wjdgx.cn.gov.cn.wjdgx.cn http://www.morning.mdgpp.cn.gov.cn.mdgpp.cn http://www.morning.rtsx.cn.gov.cn.rtsx.cn http://www.morning.zrhhb.cn.gov.cn.zrhhb.cn http://www.morning.yqsr.cn.gov.cn.yqsr.cn http://www.morning.nsjpz.cn.gov.cn.nsjpz.cn http://www.morning.qtqk.cn.gov.cn.qtqk.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.ryzgp.cn.gov.cn.ryzgp.cn http://www.morning.zmtrk.cn.gov.cn.zmtrk.cn
