网站建设中页面模板,免费自助制作永久网站,为网站添加isapi扩展,html5手机资讯网站模板题目#xff1a; 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性#xff1a;val 和 next。val 是当前节点的值#xff0c;next 是指向下一个节点的指针/引用。如果要使用双向链表#xff0c;则还需要一个属性 prev 以指示链表中的上一个节…题目 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性val 和 next。val 是当前节点的值next 是指向下一个节点的指针/引用。如果要使用双向链表则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能
get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。
示例 MyLinkedList linkedList new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1- 2- 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1- 3 linkedList.get(1); //返回3 思路创建MyLinkedList 类在类中创建ListNode 结构体结构体中创建两个成员变量并创建初始化的构造函数创建成员变量size和哨兵节点在MyLinkedList构造函数中初始化size和哨兵节点在删除元素时应该找到删除索引位置的前一个位置再删除元素。 代码
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
using namespace std;
class MyLinkedList {
public://定义链表结点结构体struct ListNode {int val;//结构体的成员变量整数类型的valListNode* next;//结构体的成员变量指向另一个ListNode对象的指针next//用于初始化节点的值和指向下一个节点的指针这个构造函数在创建新结点时被调用// 从而避免了在创建新节点后手动初始化节点的值和指针ListNode(int val) :val(val), next(nullptr) {}};//初始化链表MyLinkedList() {_size 0;//初始化为一个ListNode对象并且该节点的val成员变量被设置为0//用于表示虚拟头节点的默认值_dummyHead new ListNode(0);}//使用尾插法先插入元素void addAtTail(int val) {//创建一个新节点ListNode* newNode new ListNode(val);//从虚拟头节点开始遍历找到链表的最后一个节点ListNode* curr _dummyHead;while (curr-next) {curr curr-next;}curr-next newNode;_size;//更新链表的大小}//获取到第index个节点数值如果index是非法数值直接返回-1 //注意index是从0开始的第0个节点就是头结点int get(int index) {if (index_size-1||_size0) {return -1;}ListNode* cur _dummyHead-next;while (index) { cur cur-next;index--;}return cur-val;}//在链表最前面插入一个节点插入完成后新插入的节点为链表的新的头节点void addAtHead(int val) {ListNode* NewNode new ListNode(val);NewNode-next _dummyHead-next;_dummyHead-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;ListNode* newNode new ListNode(val);ListNode* cur _dummyHead;while (index) {cur cur-next;index--;}newNode-next cur-next;cur-next newNode;_size;}// 删除第index个节点如果index 大于等于链表的长度直接return//注意index是从0开始的void deleteAtIndex(int index) {if (index _size||index0)return;ListNode* cur _dummyHead;while (index) {cur cur-next;index--;}ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;_size--;}void printl() {ListNode* cur _dummyHead-next;while (cur) {cout cur-val -;cur cur-next;}cout NULL endl;cout 总元素个数为 _size;}
private:int _size;ListNode* _dummyHead;
};
int main() {MyLinkedList linkedList;linkedList.addAtTail(100);linkedList.addAtTail(200);linkedList.addAtTail(300);linkedList.addAtHead(66);linkedList.addAtIndex(1, 88);linkedList.deleteAtIndex(3);linkedList.printl();return 0;
}
