【中等】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 解决方法

视频链接：代码随想录：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; //声明链表长度 };