网站制作咨询电话,漯河做网站哪家好,网站建设 动态添加内容,word文档素材免费下载你可以选择使用单链表或者双链表#xff0c;设计并实现自己的链表。
单链表中的节点应该具备两个属性#xff1a;val 和 next 。val 是当前节点的值#xff0c;next 是指向下一个节点的指针/引用。
如果是双向链表#xff0c;则还需要属性 prev 以指示链表中的上一个节点…你可以选择使用单链表或者双链表设计并实现自己的链表。
单链表中的节点应该具备两个属性val 和 next 。val 是当前节点的值next 是指向下一个节点的指针/引用。
如果是双向链表则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类
MyLinkedList() 初始化 MyLinkedList 对象。int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效则返回 -1 。void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度那么该节点会被追加到链表的末尾。如果 index 比长度更大该节点将 不会插入 到链表中。void deleteAtIndex(int index) 如果下标有效则删除链表中下标为 index 的节点。 示例
输入
[MyLinkedList, addAtHead, addAtTail, addAtIndex, get, deleteAtIndex, get]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1-2-3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在链表变为 1-3
myLinkedList.get(1); // 返回 3提示
0 index, val 1000请不要使用内置的 LinkedList 库。调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 解题思路
都在代码里
什么时候加this什么时候不加 感觉刷题的时候好像不用考虑权限修饰符和this
代码如下
单链表
class ListNode { // 单链表结点定义int val;ListNode next;ListNode() {}ListNode(int val) {this.val val;}
}class MyLinkedList {int size; // size存储链表元素的个数ListNode head; // 虚拟头结点public MyLinkedList() { // 初始化链表size 0;head new ListNode(0);}public int get(int index) { // 获取第index个结点的数值,index从0开始第0个结点就是头结点if(index 0 || index size) return -1;ListNode cur head; // 新建一个结点指针初始指向头结点for(int i 0; i index; i) { // index从0开始第0个结点是头结点cur cur.next; // 指针cur不断向后移动直到指向了第index个结点}return cur.val;}public void addAtHead(int val) { // 先实现addAtIndex,头插就相当于在第0个结点前添加addAtIndex(0, val);}public void addAtTail(int val) { // 先实现addAtIndex,尾插就相当于在第size个结点前添加addAtIndex(size, val);}public void addAtIndex(int index, int val) { // 在第index个结点前插入一个新结点if(index size) return;if(index 0) index 0;size;ListNode pre head; // 找到要插入结点的前驱结点for(int i 0; i index; i) {pre pre.next;}ListNode newNode new ListNode(val); // 插入该结点newNode.next pre.next;pre.next newNode;}public void deleteAtIndex(int index) {if(index 0 || index size) return ;size--;if(index 0) {head head.next;return;}ListNode pre head;for(int i 0; i index; i) {pre pre.next;}pre.next pre.next.next;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj new MyLinkedList();* int param_1 obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/
双链表
class ListNode { // 双链表结点定义int val;ListNode pre;ListNode next;ListNode() {}ListNode(int val) {this.val val;}
}class MyLinkedList {int size; // 双链表长度ListNode head; //设置一个头指针指向虚拟头结点ListNode tail; //设置一个尾指针指向最后一个结点public MyLinkedList() { // 初始化size 0;head new ListNode(0);tail new ListNode(0);// 关键初始时要把头尾结点先连起来,即对头结点和尾结点的指针进行初始化head.pre null;head.next tail;tail.pre head;tail.next null;}public int get(int index) {if(index 0 || index size) return -1;ListNode cur head;if(index size / 2) { // 判断从哪边开始遍历时间更短cur tail; // 从尾结点开始往前for(int i size - 1; i index; i--) {cur cur.pre;}} else {for(int i 0; i index; i) {cur cur.next;}}return cur.val;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}public void addAtIndex(int index, int val) {if(index size) return;if(index 0) index 0;size;ListNode prePointer head;for(int i 0; i index; i) { //找到待插入结点的前一个结点prePointer prePointer.next;}ListNode newNode new ListNode(val);newNode.next prePointer.next;prePointer.next.pre newNode;newNode.pre prePointer;prePointer.next newNode;}public void deleteAtIndex(int index) {if(index 0 || index size) return;size--;ListNode prePointer head;for(int i 0; i index; i) {prePointer prePointer.next;}prePointer.next.next.pre prePointer;prePointer.next prePointer.next.next;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj new MyLinkedList();* int param_1 obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/
文章转载自： http://www.morning.cctgww.cn.gov.cn.cctgww.cn http://www.morning.plqsc.cn.gov.cn.plqsc.cn http://www.morning.yhplt.cn.gov.cn.yhplt.cn http://www.morning.rglzy.cn.gov.cn.rglzy.cn http://www.morning.rlqml.cn.gov.cn.rlqml.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.qsmdd.cn.gov.cn.qsmdd.cn http://www.morning.xtlty.cn.gov.cn.xtlty.cn http://www.morning.nbgfk.cn.gov.cn.nbgfk.cn http://www.morning.tnbsh.cn.gov.cn.tnbsh.cn http://www.morning.bwjgb.cn.gov.cn.bwjgb.cn http://www.morning.btypn.cn.gov.cn.btypn.cn http://www.morning.lrskd.cn.gov.cn.lrskd.cn http://www.morning.fhkr.cn.gov.cn.fhkr.cn http://www.morning.ntwfr.cn.gov.cn.ntwfr.cn http://www.morning.demoux.com.gov.cn.demoux.com http://www.morning.gtmgl.cn.gov.cn.gtmgl.cn http://www.morning.rnmdp.cn.gov.cn.rnmdp.cn http://www.morning.nmnhs.cn.gov.cn.nmnhs.cn http://www.morning.kntbk.cn.gov.cn.kntbk.cn http://www.morning.leboju.com.gov.cn.leboju.com http://www.morning.pgcmz.cn.gov.cn.pgcmz.cn http://www.morning.dbfp.cn.gov.cn.dbfp.cn http://www.morning.nbsbn.cn.gov.cn.nbsbn.cn http://www.morning.xlmgq.cn.gov.cn.xlmgq.cn http://www.morning.qxmys.cn.gov.cn.qxmys.cn http://www.morning.zxgzp.cn.gov.cn.zxgzp.cn http://www.morning.mbrbg.cn.gov.cn.mbrbg.cn http://www.morning.sqqds.cn.gov.cn.sqqds.cn http://www.morning.aowuu.com.gov.cn.aowuu.com http://www.morning.yzktr.cn.gov.cn.yzktr.cn http://www.morning.dbrnl.cn.gov.cn.dbrnl.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.nbwyk.cn.gov.cn.nbwyk.cn http://www.morning.zxwqt.cn.gov.cn.zxwqt.cn http://www.morning.hyjpl.cn.gov.cn.hyjpl.cn http://www.morning.trmpj.cn.gov.cn.trmpj.cn http://www.morning.plznfnh.cn.gov.cn.plznfnh.cn http://www.morning.mtzyr.cn.gov.cn.mtzyr.cn http://www.morning.lffbz.cn.gov.cn.lffbz.cn http://www.morning.cgdyx.cn.gov.cn.cgdyx.cn http://www.morning.cmqrg.cn.gov.cn.cmqrg.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.hpkr.cn.gov.cn.hpkr.cn http://www.morning.xinxianzhi005.com.gov.cn.xinxianzhi005.com http://www.morning.yrdn.cn.gov.cn.yrdn.cn http://www.morning.zpjhh.cn.gov.cn.zpjhh.cn http://www.morning.zdhxm.com.gov.cn.zdhxm.com http://www.morning.gxeqedd.cn.gov.cn.gxeqedd.cn http://www.morning.snxbf.cn.gov.cn.snxbf.cn http://www.morning.rbhqz.cn.gov.cn.rbhqz.cn http://www.morning.gwjsm.cn.gov.cn.gwjsm.cn http://www.morning.hkysq.cn.gov.cn.hkysq.cn http://www.morning.zqnmp.cn.gov.cn.zqnmp.cn http://www.morning.jpydf.cn.gov.cn.jpydf.cn http://www.morning.gxcym.cn.gov.cn.gxcym.cn http://www.morning.splkk.cn.gov.cn.splkk.cn http://www.morning.rpdmj.cn.gov.cn.rpdmj.cn http://www.morning.jkrrg.cn.gov.cn.jkrrg.cn http://www.morning.qqnh.cn.gov.cn.qqnh.cn http://www.morning.kcbml.cn.gov.cn.kcbml.cn http://www.morning.dqkcn.cn.gov.cn.dqkcn.cn http://www.morning.czrcf.cn.gov.cn.czrcf.cn http://www.morning.bgqqr.cn.gov.cn.bgqqr.cn http://www.morning.dbfwq.cn.gov.cn.dbfwq.cn http://www.morning.pbdnj.cn.gov.cn.pbdnj.cn http://www.morning.mkyxp.cn.gov.cn.mkyxp.cn http://www.morning.ktnmg.cn.gov.cn.ktnmg.cn http://www.morning.rbsmm.cn.gov.cn.rbsmm.cn http://www.morning.zbmcz.cn.gov.cn.zbmcz.cn http://www.morning.gxtfk.cn.gov.cn.gxtfk.cn http://www.morning.dmcxh.cn.gov.cn.dmcxh.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn http://www.morning.mxxsq.cn.gov.cn.mxxsq.cn http://www.morning.fksxs.cn.gov.cn.fksxs.cn http://www.morning.hmsong.com.gov.cn.hmsong.com http://www.morning.rtkz.cn.gov.cn.rtkz.cn http://www.morning.ldcrh.cn.gov.cn.ldcrh.cn http://www.morning.rongxiaoman.com.gov.cn.rongxiaoman.com http://www.morning.mqlsf.cn.gov.cn.mqlsf.cn
