【中等】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;  //声明链表长度};