网站运营是具体的,wordpress 移动端 搜索,君卓展览的售后服务,网络推广的几种主要方法707.设计链表 你可以选择使用单链表或者双链表#xff0c;设计并实现自己的链表。 单链表中的节点应该具备两个属性#xff1a;val 和 next 。val 是当前节点的值#xff0c;next 是指向下一个节点的指针/引用。 如果是双向链表#xff0c;则还需要属性 prev 以指示链表中的…707.设计链表 你可以选择使用单链表或者双链表设计并实现自己的链表。 单链表中的节点应该具备两个属性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 。 单链表
// 定义链表节点类
class ListNode {int val; // 节点存储的值ListNode next; // 指向下一个节点的指针// 无参构造方法ListNode() {}// 带参数构造方法ListNode(int val) {this.val val;}
}// 实现单链表的类
class MyLinkedList {int size; // 链表的长度节点数ListNode head; // 虚拟头节点方便统一操作// 初始化链表MyLinkedList() {head new ListNode(0); // 初始化虚拟头节点size 0; // 初始化链表长度为 0}// 获取指定索引处的值public int get(int index) {// 如果索引非法返回 -1if (index 0 || index size) {return -1;}// 从虚拟头节点的下一个节点开始遍历ListNode cur head.next;for (int i 0; i index; i) {cur cur.next; // 移动到下一个节点}// 返回指定节点的值return cur.val;}// 在链表头部插入值为 val 的节点public void addAtHead(int val) {// 创建新节点ListNode cur new ListNode(val);// 新节点的 next 指向当前链表的第一个节点cur.next head.next;// 虚拟头节点的 next 指向新节点head.next cur;// 链表长度加 1size;}// 在链表尾部插入值为 val 的节点public void addAtTail(int val) {// 创建新节点ListNode cur head; // 从虚拟头节点开始遍历ListNode tail new ListNode(val); // 新的尾部节点// 遍历链表找到最后一个节点for (int i 0; i size; i) {cur cur.next;}// 将最后一个节点的 next 指向新节点cur.next tail;// 链表长度加 1size;}// 在指定索引处插入值为 val 的节点public void addAtIndex(int index, int val) {// 如果索引超过当前链表长度不进行插入操作if (index size) {return;}// 如果索引小于 0将索引置为 0if (index 0) {index 0;}// 创建新节点ListNode cur head; // 从虚拟头节点开始遍历ListNode addNode new ListNode(val); // 要插入的节点// 遍历到指定索引位置的前一个节点for (int i 0; i index; i) {cur cur.next;}// 插入新节点addNode.next cur.next; // 新节点的 next 指向当前索引位置的节点cur.next addNode; // 当前节点的 next 指向新节点size; // 链表长度加 1}// 删除指定索引处的节点public void deleteAtIndex(int index) {// 如果索引非法不进行删除操作if (index 0 || index size) {return;}// 从虚拟头节点开始遍历ListNode cur head;// 遍历到指定索引位置的前一个节点for (int i 0; i index; i) {cur cur.next;}// 删除节点当前节点的 next 指向被删除节点的下一个节点cur.next cur.next.next;size--; // 链表长度减 1}
}双链表
class ListDoubleNode{int val;ListDoubleNode prev,next;ListDoubleNode(){};ListDoubleNode(int val){this.valval;};
}
class MyLinkedListSolution1 {int size;ListDoubleNode head,tail;public MyLinkedListSolution1() {//初始化操作this.size 0;this.head new ListDoubleNode(0);this.tail new ListDoubleNode(0);//这一步非常关键否则在加入头结点的操作中会出现null.next的错误head.nexttail;tail.prevhead;}public int get(int index) {//判断index是否有效if(indexsize){return -1;}ListDoubleNode cur this.head;//判断是哪一边遍历时间更短if(index size / 2){//tail开始cur tail;for(int i0; i size-index; i){cur cur.prev;}}else{for(int i0; i index; i){cur cur.next;}}return cur.val;}public void addAtHead(int val) {//等价于在第0个元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等价于在最后一个元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于链表长度if(indexsize){return;}size;//找到前驱ListDoubleNode pre this.head;for(int i0; iindex; i){pre pre.next;}//新建结点ListDoubleNode newNode new ListDoubleNode(val);newNode.next pre.next;pre.next.prev newNode;newNode.prev pre;pre.next newNode;}public void deleteAtIndex(int index) {//判断索引是否有效if(indexsize){return;}//删除操作size--;ListDoubleNode pre this.head;for(int i0; iindex; i){pre pre.next;}pre.next.next.prev pre;pre.next pre.next.next;}
}
