leetcode707----设计链表【链表增删改打印等操作】

目录

一、题目介绍

 二、单链表

2.1 创建链表类 

2.1.1 定义链表节点结构体代码块

2.1.2 MyLinkedList类的构造函数

2.1.3 私有成员变量

2.2 接口1：获取第下标为index的节点的值

2.3 接口2：头部插入节点

2.4 接口3：尾部插入节点

2.5 接口4：在下标为index的节点前插入新节点

2.6 接口5：删除下标为index的节点

2.7 打印链表

2.8 主函数部分

2.9 总体代码

---

一、题目介绍

题目链接：707. 设计链表 - 力扣（LeetCode）

题目简介 

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：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 的节点。

题目分析： 

这道题目设计链表的五个接口：

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点

可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目

链表操作的两种方式：

1. 直接使用原来的链表来进行操作。
2. 设置一个虚拟头结点在进行操作。

下面采用的设置一个虚拟头结点（这样更方便一些，大家看代码就会感受出来）。

 二、单链表

2.1 创建链表类 

 类的成员（包括嵌套结构体）默认是私有的，除非你显式指定它们为公有的（public）。

#include<iostream>
class MyLinkedList{public:// 定义链表节点结构体struct LinkedNode{int val; // 单链表的数据域LinkedNode* next; // 单链表的指针域LinkedNode(int x):val(x),next(nullptr){} // 节点的构造函数};// 初始化链表，MyLinkedList的构造函数MyLinkedList(){virtualHead = new LinkedNode(0); // 定义虚拟头节点ListSize = 0; // 链表的初始长度置为 0  }private:LinkedNode* virtualHead; // 链表的虚拟节点int ListSize; // 链表的长度};

2.1.1 定义链表节点结构体代码块

 // 定义链表节点结构体struct LinkedNode{int val; // 单链表的数据域LinkedNode* next; // 单链表的指针域LinkedNode(int x):val(x),next(nullptr){} // 节点的构造函数};

• LinkedNode 是链表的节点结构体。每个节点包含两个成员：

  • val：存储节点的数据，类型为 int。
  • next：指向下一个节点的指针。若该节点为链表的最后一个节点，则 next 为 nullptr。

• 构造函数 LinkedNode(int x) 用于初始化节点的值，并将 next 指针初始化为 nullptr，表示该节点暂时没有指向任何其他节点。

2.1.2 MyLinkedList类的构造函数

MyLinkedList() {virtualHead = new LinkedNode(0); // 定义虚拟头节点ListSize = 0; // 链表的初始长度置为 0  
}

• MyLinkedList 是 MyLinkedList 类的构造函数，用于初始化链表。
• virtualHead = new LinkedNode(0)：这里创建了一个 虚拟头节点，它的值为 0，并且 next 指向 nullptr。虚拟头节点通常用于简化链表的操作，避免在处理链表时需要单独处理头节点（例如插入、删除操作时）。
• ListSize = 0：初始化链表的长度为 0，因为此时链表是空的。

2.1.3 私有成员变量

private:LinkedNode* virtualHead; // 链表的虚拟节点int ListSize; // 链表的长度

• virtualHead：指向链表虚拟头节点的指针。虚拟头节点本身不存储有效数据，它的存在是为了简化链表操作，尤其是在进行头节点的插入和删除时。
• ListSize：一个整数，表示链表的当前大小。每当进行节点的插入或删除时，ListSize 会相应更新。

2.2 接口1：获取第下标为index的节点的值

 //int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。// 注意index是从0开始的，第0个节点就是头结点，即链表中第一个节点int get(int index){// 判断链表是否为空if(virtualHead->next == nullptr){return -1;}else{ // 链表非空// 首先判断下标的有效性if(index >(ListSize - 1) || index < 0){return -1;}// 下标有效，开始寻找下标为index的节点的值LinkedNode* ptr = virtualHead->next; // 定义遍历链表的指针while(index){ // 假设要遍历下标为0的节点，即链表的第1个节点，链表的头节点，index=0不符合while条件，直接返回ptr->valptr=ptr->next;index--;}return ptr->val;}   }

这段代码实现了一个 get 函数，用于获取链表中指定下标 index 的节点值。它首先检查链表是否为空若为空，直接返回-1，若不为空，再检查下标的有效性，然后遍历链表找到对应下标的节点，并返回该节点的值。 

可能的优化与改进：

1. 性能考虑：

   • 目前的实现是线性时间复杂度 O(n)，因为需要遍历链表中的 index+1【index表示的是下标索引，从0开始的】 个节点。如果链表很长，查找某个节点的值会比较慢。
   • 对于更高效的实现，可以考虑维护一个指向链表尾部的指针，这样在获取末尾节点时可以更快地实现从两端往中间遍历。【双向链表实现】

2.3 接口2：头部插入节点

// void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtHead(int val){LinkedNode* NewHead= new LinkedNode(val); // 定义头插节点LinkedNode* OldHead = virtualHead->next; virtualHead->next = NewHead;// 虚拟头节点的指针域存放新的头节点的地址NewHead->next=OldHead;// 新头节点的指针域存放旧的头节点的地址ListSize++;// 添加一个新的头节点之后，链表的长度+1}

2.4 接口3：尾部插入节点

// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。void addAtTail(int val){LinkedNode* NewNode = new LinkedNode(val);LinkedNode* ptr = virtualHead->next; // 定义一个遍历链表的指针while(ptr->next!=nullptr){ // ptr->next!=nullptr说明当前节点的下一个节点是存在的，如果ptr->next=nullptr，说明当前节点的下一个节点不存在，此时遍历到链表的尾端ptr = ptr->next;}ptr->next=NewNode;ListSize++;}

2.5 接口4：在下标为index的节点前插入新节点

//void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。//如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。void addAtIndex(int index, int val){// 判断index的有效性if(index<0|| index>ListSize){ //下标越界std::cout<<"下标 index 越界!" <<std::endl;}if(index==ListSize){ // 若插入的下标值等于链表的原长度，那采用链表的尾插法进行插入addAtTail(val); // 直接调用尾插法函数}if(index==0){  // 若插入的下标值等于0，那采用链表的头插法进行插入addAtHead(val); // 直接调用头插法函数}LinkedNode* IndexNode = new LinkedNode(val); // 创建要插入的节点LinkedNode* ptr = virtualHead; // 定义遍历指针while(index){ // 找到下标为index的位置ptr = ptr->next; // 遍历指针依次后移index--;}IndexNode->next = ptr->next;ptr->next = IndexNode;ListSize++;}

2.6 接口5：删除下标为index的节点

// 链表的节点删除操作// void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。void deleteAtIndex(int index){// 判断下标的合理性if(index<0||index>ListSize-1){std::cout<<"下标 index 越界!"<<std::endl;}else{LinkedNode* Ptr = virtualHead; // 遍历指针while(index){ // 找出下标为 index 的节点Ptr=Ptr->next; index--;}Ptr->next = Ptr->next->next; // 删除操作LinkedNode* DeletePtr = Ptr->next; // Deleteptr指向待删除的节点delete DeletePtr;//delete命令只是释放了DeletePtr指针原本所指的那部分内存，//被delete后的指针DeletePtr的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句DeletePtr=nullptr,DeletePtr会成为乱指的野指针//如果之后的程序不小心使用了DeletePtr，会指向难以预想的内存空间DeletePtr=nullptr;ListSize--; // 删除链表一个节点，链表长度-1}}

2.7 打印链表

// 打印链表中所有的元素void PrintList(){LinkedNode* ptr = virtualHead; // 定义遍历指针while(ptr->next!=nullptr){ // std::cout<<ptr->next->val<<" ";ptr = ptr->next;}std::cout<<std::endl;}

2.8 主函数部分

int main(){MyLinkedList List; // 实例化对象// List.addAtHead(1); // 头插法// List.addAtHead(2); // 头插法// List.addAtHead(3); // 头插法// List.addAtTail(4); // 尾插法// List.PrintList(); // 打印链表中的所有元素// List.addAtIndex(2,5); // 在指定的索引位置处插入新元素// List.PrintList(); // 打印链表中的所有元素// List.deleteAtIndex(6); // 删除指定的索引位置的节点// List.PrintList(); // 打印链表中的所有元素int index_get = 2;int get_ = List.get(index_get); // 获取指定索引位置处的元素if(get_){ // 链表为空时，get函数返回-1，-1=True std::cout<<"链表为空!"<<std::endl;}else{std::cout<<"索引位置为:"<<index_get<<"的值为:"<<get_<<std::endl;}   
}

2.9 总体代码

#include<iostream>
class MyLinkedList{public:// 定义链表节点结构体struct LinkedNode{int val; // 单链表的数据域LinkedNode* next; // 单链表的指针域LinkedNode(int x):val(x),next(nullptr){} // 节点的构造函数};// 初始化链表，MyLinkedList的构造函数MyLinkedList(){virtualHead = new LinkedNode(0); // 定义虚拟头节点ListSize = 0; // 链表的初始长度置为 0  }//int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。// 注意index是从0开始的，第0个节点就是头结点，即链表中第一个节点int get(int index){// 判断链表是否为空if(virtualHead->next == nullptr){return -1;}else{ // 链表非空// 首先判断下标的有效性if(index >(ListSize - 1) || index < 0){return -1;}// 下标有效，开始寻找下标为index的节点的值LinkedNode* ptr = virtualHead->next; // 定义遍历链表的指针while(index){ // 假设要遍历下标为0的节点，即链表的第1个节点，链表的头节点，index=0不符合while条件，直接返回ptr->valptr=ptr->next;index--;}return ptr->val;}   }// void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtHead(int val){LinkedNode* NewHead= new LinkedNode(val); // 定义头插节点LinkedNode* OldHead = virtualHead->next; virtualHead->next = NewHead;// 虚拟头节点的指针域存放新的头节点的地址NewHead->next=OldHead;// 新头节点的指针域存放旧的头节点的地址ListSize++;// 添加一个新的头节点之后，链表的长度+1}// void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。void addAtTail(int val){LinkedNode* NewNode = new LinkedNode(val);LinkedNode* ptr = virtualHead->next; // 定义一个遍历链表的指针while(ptr->next!=nullptr){ // ptr->next!=nullptr说明当前节点的下一个节点是存在的，如果ptr->next=nullptr，说明当前节点的下一个节点不存在，此时遍历到链表的尾端ptr = ptr->next;}ptr->next=NewNode;ListSize++;}//void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。//如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。void addAtIndex(int index, int val){// 判断index的有效性if(index<0|| index>ListSize){ //下标越界std::cout<<"下标 index 越界!" <<std::endl;}if(index==ListSize){ // 若插入的下标值等于链表的原长度，那采用链表的尾插法进行插入addAtTail(val); // 直接调用尾插法函数}if(index==0){  // 若插入的下标值等于0，那采用链表的头插法进行插入addAtHead(val); // 直接调用头插法函数}LinkedNode* IndexNode = new LinkedNode(val); // 创建要插入的节点LinkedNode* ptr = virtualHead; // 定义遍历指针while(index){ // 找到下标为index的位置ptr = ptr->next; // 遍历指针依次后移index--;}IndexNode->next = ptr->next;ptr->next = IndexNode;ListSize++;}// 链表的节点删除操作// void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。void deleteAtIndex(int index){// 判断下标的合理性if(index<0||index>ListSize-1){std::cout<<"下标 index 越界!"<<std::endl;}else{LinkedNode* Ptr = virtualHead; // 遍历指针while(index){ // 找出下标为 index 的节点Ptr=Ptr->next; index--;}Ptr->next = Ptr->next->next; // 删除操作LinkedNode* DeletePtr = Ptr->next; // Deleteptr指向待删除的节点delete DeletePtr;//delete命令只是释放了DeletePtr指针原本所指的那部分内存，//被delete后的指针DeletePtr的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句DeletePtr=nullptr,DeletePtr会成为乱指的野指针//如果之后的程序不小心使用了DeletePtr，会指向难以预想的内存空间DeletePtr=nullptr;ListSize--; // 删除链表一个节点，链表长度-1}}// 打印链表中所有的元素void PrintList(){LinkedNode* ptr = virtualHead; // 定义遍历指针while(ptr->next!=nullptr){ // std::cout<<ptr->next->val<<" ";ptr = ptr->next;}std::cout<<std::endl;}private:LinkedNode* virtualHead; // 链表的虚拟节点int ListSize; // 链表的长度};int main(){MyLinkedList List; // 实例化对象// List.addAtHead(1); // 头插法// List.addAtHead(2); // 头插法// List.addAtHead(3); // 头插法// List.addAtTail(4); // 尾插法// List.PrintList(); // 打印链表中的所有元素// List.addAtIndex(2,5); // 在指定的索引位置处插入新元素// List.PrintList(); // 打印链表中的所有元素// List.deleteAtIndex(6); // 删除指定的索引位置的节点// List.PrintList(); // 打印链表中的所有元素int index_get = 2;int get_ = List.get(index_get); // 获取指定索引位置处的元素if(get_){ // 链表为空时，get函数返回-1，-1=True std::cout<<"链表为空!"<<std::endl;}else{std::cout<<"索引位置为:"<<index_get<<"的值为:"<<get_<<std::endl;}   
}

推荐观看视频： 

 帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili