LeetCode 707. 设计链表

LeetCode 707. 设计链表

难度：$middle$

---

题目描述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：$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

提示：

• $0<=index,val<=1000$
• 请不要使用内置的 LinkedList 库。
• $get$, $addAtHead$, $addAtTail$, $addAtIndex$ 和 $deleteAtIndex$ 的操作次数不超过 $2000$。

---

算法1

(单链表)

实现单向链表，即每个节点仅存储本身的值和后继节点。除此之外，我们还需要一个哨兵（sentinel）节点作为头节点，和一个 size 参数保存有效节点数。如下图所示。

复杂度分析

• 时间复杂度：$O(n)$，初始化消耗 $O(1)$，get 消耗 $O(index)$，addAtHead 消耗 $O(1)$，addAtTail 消耗 $O(n)$，其中 n 为链表当前长度。

• 空间复杂度 : 所有函数的单次调用空间复杂度均为 $O(1)$，总体空间复杂度为 $O(n)$。

C++ 代码

class MyLinkedList {
public:struct Node {int val;Node* next;Node(int _val): val(_val), next(NULL) {}}*head;MyLinkedList() {head = NULL;}int get(int index) {if (index < 0) return -1;auto p = head;for (int i = 0; i < index && p; i ++ ) p = p->next;if (!p) return -1;return p->val;}void addAtHead(int val) {auto cur = new Node(val);cur->next = head;head = cur;}void addAtTail(int val) {if (!head) head = new Node(val);else {auto p = head;while (p->next) p = p->next;p->next = new Node(val); }}void addAtIndex(int index, int val) {if (index <= 0) addAtHead(val);else {int len = 0;for (auto p = head; p; p = p->next) len ++ ;if (index == len) addAtTail(val);else if (index < len) {auto p = head;for (int i = 0; i < index - 1; i ++ ) p = p->next;auto cur = new Node(val);cur->next = p->next;p->next = cur;} }       }void deleteAtIndex(int index) {int len = 0;for (auto p = head; p; p = p->next) len ++ ;if (index >= 0 && index < len) {if (index == 0) head = head->next;else {auto p = head;for (int i = 0; i < index - 1; i ++ ) p = p->next;p->next = p->next->next;}}}
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/

---

---

算法2

(双链表)

实现双向链表，即每个节点要存储本身的值，后继节点和前驱节点。除此之外，需要一个哨兵节点作为头节点 head 和一个哨兵节点作为尾节点 tail。仍需要一个 size 参数保存有效节点数。如下图所示。

复杂度分析

• 时间复杂度：$O(n)$，初始化消耗 $O(1)$，get 消耗 $O(index)$，addAtHead 消耗 $O(1)$，addAtTail 消耗 $O(n)$，其中 n 为链表当前长度。

• 空间复杂度 : 所有函数的单次调用空间复杂度均为 $O(1)$，总体空间复杂度为 $O(n)$。

C++ 代码

class MyLinkedList {
public://双链表struct Node {Node *left, *right;int val;Node(int _val) {val = _val;left = right = NULL;}}*head, *tail;//表示节点的个数int size;//初始化MyLinkedList() {size = 0;head = new Node(INT_MIN), tail = new Node(INT_MAX);head->right = tail;tail->left = head;}int get(int index) {if (index < 0 || index >= size)return -1;//找到第 index 个节点，head是虚拟节点，所以 i <= indexauto p = head;for (int i = 0; i <= index; i ++) p = p->right;return p->val;  }void addAtHead(int val) {auto t = new Node(val);size ++;t->right = head->right, head->right->left = t;t->left = head, head->right = t;}void addAtTail(int val) {auto t = new Node(val);size ++;tail->left->right = t, t->left = tail->left;t->right = tail, tail->left = t;}void addAtIndex(int index, int val) {if (index > size) return;else if (index == size) addAtTail(val);else if (index < 0) addAtHead(val);else {auto p = head;//在链表中的第 index 个节点之前添加值为 val  的节点，所以找到第 index-1 节点，在后面插入一个节点for (int i = 0; i < index; i ++)p = p->right;auto q = p->right;size ++;auto t = new Node(val);t->right = q, q->left = t;p->right = t, t->left = p;}}   void deleteAtIndex(int index) {if (index < 0 || index >= size) return;auto p = head;// p 是虚拟节点，p点是要删除的节点for (int i = 0; i <= index; i ++) p = p->right;size --;p->right->left = p->left;p->left->right = p->right;delete p;}
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/