高端网站建设公司怎么做推广,守游网络推广平台登陆,微信营销教程,百度站长官网题目描述
你可以选择使用单链表或者双链表#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解决方法
视频链接代码随想录707.设计链表 这道题目设计链表的五个接口
获取链表第index个节点的数值 在链表的最前面插入一个节点 在链表的最后面插入一个节点 在链表第index个节点前面插入一个节点 删除链表的第index个节点 可以说这五个接口已经覆盖了链表的常见操作是练习链表操作非常好的一道题目
可参考代码随想录
方法一虚拟头节点
设置虚拟头结点让原来的头结点和后面的结点的处理方式一致更方便
class MyLinkedList {
public:// 定义链表结点结构体struct LinkedNode{int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};//初始化链表MyLinkedList() {_dummyHead new LinkedNode(0); //定义虚拟头结点_size 0;}// 获取到第index个结点数值如果非法返回-1 从0开始int get(int index) {if(index (_size - 1) || index 0){return -1;}LinkedNode* cur _dummyHead-next;while(index--) //如果--index就会陷入死循环{cur cur-next;}return cur-val; }// 在链表最前面插入一个节点插入完成后新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode new LinkedNode(val);newNode-next _dummyHead-next;_dummyHead-next newNode;_size;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode new LinkedNode(val);LinkedNode* cur _dummyHead;while(cur-next ! nullptr){cur cur-next;}cur-next newNode;_size;}// 在第index个节点之前插入一个新节点例如index为0那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度则返回空// 如果index小于0则在头部插入节点void addAtIndex(int index, int val) {if(index _size){return;} if(index 0){index 0;}LinkedNode* newNode new LinkedNode(val);LinkedNode* cur _dummyHead;while(index--){cur cur-next;}newNode-next cur-next;cur-next newNode;_size;}// 删除第index个节点如果index 大于等于链表的长度直接return注意index是从0开始的void deleteAtIndex(int index) {if(index _size || index 0){return;}LinkedNode* cur _dummyHead;while(index--){cur cur-next;}LinkedNode* tmp cur-next;cur-next cur-next-next;delete tmp;tmp nullptr;_size--;}private:LinkedNode* _dummyHead; //声明虚拟头结点int _size; //声明链表长度};
时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1) 空间复杂度: O(n)
方法二双向链表法
双指针一个指向下一结点一个指向上一结点更方便插入
class MyLinkedList {
public:// 定义双向链表结点结构体struct DList{int elem;DList *next;DList *prev;DList(int elem):elem(elem), next(nullptr), prev(nullptr){};};//初始化链表MyLinkedList() {sentinelNode new DList(0); // 创建哨兵节点不存储有效数据sentinelNode-next sentinelNode; // 哨兵节点的下一个节点指向自身形成循环sentinelNode-prev sentinelNode; // 哨兵节点的上一个节点指向自身形成循环size 0;}// 获取到第index个结点数值如果非法返回-1 从0开始int get(int index) {if(index (size - 1) || index 0){return -1;}int num;int mid size 1; // 计算链表中部位置DList * cur sentinelNode; // 从哨兵节点开始if(index mid) // 如果索引小于中部位置从前往后遍历{for(int i 0; i index 1; i){cur cur-next;}}else // 如果索引大于等于中部位置从后往前遍历{for(int i 0; i size - index; i){cur cur-prev;}}num cur-elem;return num;}// 在链表最前面插入一个节点插入完成后新插入的节点为链表的新的头结点void addAtHead(int val) {DList *newNode new DList(val);DList *next sentinelNode-next; // 获取当前头节点的下一个节点newNode-prev sentinelNode; // 新节点的上一个节点指向哨兵节点newNode-next next; // 新节点的下一个节点指向原来的头节点size;sentinelNode-next newNode; // 哨兵节点的下一个节点指向新节点next-prev newNode; // 原来的头节点的上一个节点指向新节点}// 在链表最后面添加一个节点void addAtTail(int val) {DList *newNode new DList(val);DList *prev sentinelNode-prev; // 获取当前尾节点的上一个节点newNode-next sentinelNode; // 新节点的下一个节点指向哨兵节点newNode-prev prev; // 新节点的上一个节点指向原来的尾节点size;sentinelNode-prev newNode; // 哨兵节点的上一个节点指向新节点prev-next newNode; // 原来的尾节点的下一个节点指向新节点}// 在链表中的第index个节点之前添加值为val的节点void addAtIndex(int index, int val) {if(index size){return;}if(index 0){addAtHead(val); // 如果索引为0或负数在头部添加节点return;}int mid size 1; // 计算链表中部位置DList *cur sentinelNode; // 从哨兵节点开始if(index mid) // 如果索引小于中部位置从前往后遍历{for(int i 0; i index; i){cur cur-next; // 移动到目标位置的前一个节点}DList *tmp cur-next; // 获取目标位置的节点DList *newNode new DList(val); // 创建新节点cur-next newNode; // 在目标位置前添加新节点tmp-prev newNode; // 目标位置的节点的前一个节点指向新节点newNode-next tmp; // 新节点的下一个节点指向目标位置的结点newNode-prev cur; // 新节点的上一个节点指向当前节点}else // 如果索引大于等于中部位置从后往前遍历{for(int i 0; i size - index; i){cur cur-prev; // 移动到目标位置的后一个节点}DList *tmp cur-prev; // 获取目标位置的节点DList *newNode new DList(val); // 创建新节点cur-prev newNode; // 在目标位置后添加新节点tmp-next newNode; // 目标位置的节点的下一个节点指向新节点newNode-prev tmp; // 新节点的上一个节点指向目标位置的节点newNode-next cur; // 新节点的下一个节点指向当前节点}size; // 链表大小加1}// 删除第index个节点如果index 大于等于链表的长度直接return注意index是从0开始的void deleteAtIndex(int index) {if(index (size - 1) || index 0){return;}int num;int mid size 1; // 计算链表中部位置DList *cur sentinelNode;// 从哨兵节点开始if(index mid){for(int i 0; i index; i){cur cur-next;}DList *next cur-next-next; // 获取目标位置的下一个节点cur-next next; // 删除目标位置的节点next-prev cur; // 目标位置的下一个节点的前一个节点指向当前节点}else{for(int i 0; i size - index - 1; i){cur cur-prev;}DList *prev cur-prev-prev;cur-prev prev;prev-next cur;}size--;}private:DList* sentinelNode; //声明虚拟头结点int size; //声明链表长度};
