建设部机关服务中心网站,wordpress手机访问不了,家里的电脑怎样做网站赚钱,上海网络科技有限公司排名LeetCode 707. 设计链表
难度#xff1a;middle\color{orange}{middle}middle 题目描述
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性#xff1a;valvalval 和 nextnextnext。valvalval 是当前节点的值#xff0c;nextnextnext 是指向下…LeetCode 707. 设计链表
难度middle\color{orange}{middle}middle 题目描述
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性valvalval 和 nextnextnext。valvalval 是当前节点的值nextnextnext 是指向下一个节点的指针/引用。如果要使用双向链表则还需要一个属性 prevprevprev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能
get(index)获取链表中第 indexindexindex 个节点的值。如果索引无效则返回−1-1−1。addAtHead(val)在链表的第一个元素之前添加一个值为 valvalval 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 valvalval 的节点追加到链表的最后一个元素。addAtIndex(index,val)在链表中的第 indexindexindex 个节点之前添加值为 valvalval 的节点。如果 indexindexindex 等于链表的长度则该节点将附加到链表的末尾。如果 indexindexindex 大于链表长度则不会插入节点。如果indexindexindex小于0则在头部插入节点。deleteAtIndex(index)如果索引 indexindexindex 有效则删除链表中的第 indexindexindex 个节点。
示例
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提示
0index,val10000 index, val 10000index,val1000请不要使用内置的 LinkedList 库。getgetget, addAtHeadaddAtHeadaddAtHead, addAtTailaddAtTailaddAtTail, addAtIndexaddAtIndexaddAtIndex 和 deleteAtIndexdeleteAtIndexdeleteAtIndex 的操作次数不超过 200020002000。 算法1
(单链表)
实现单向链表即每个节点仅存储本身的值和后继节点。除此之外我们还需要一个哨兵sentinel节点作为头节点和一个 size 参数保存有效节点数。如下图所示。 复杂度分析 时间复杂度O(n)O(n)O(n)初始化消耗 O(1)O(1)O(1)get 消耗 O(index)O(index)O(index)addAtHead 消耗 O(1)O(1)O(1)addAtTail 消耗 O(n)O(n)O(n)其中 n 为链表当前长度。 空间复杂度 : 所有函数的单次调用空间复杂度均为 O(1)O(1)O(1)总体空间复杂度为 O(n)O(n)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(n)O(n)初始化消耗 O(1)O(1)O(1)get 消耗 O(index)O(index)O(index)addAtHead 消耗 O(1)O(1)O(1)addAtTail 消耗 O(n)O(n)O(n)其中 n 为链表当前长度。 空间复杂度 : 所有函数的单次调用空间复杂度均为 O(1)O(1)O(1)总体空间复杂度为 O(n)O(n)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);*/
