707.?設L計鏈表

中等

902

相關企業

你可以選擇使用單鏈表或者雙鏈表，設計并實現自己的鏈表。

單鏈表中的節點應該具備兩個屬性：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

struct linkednode{int val;linkednode* next;linkednode(int val): val(val),next(NULL){}
};
class MyLinkedList {
private:linkednode * _dummynode;int _size;
public:MyLinkedList() {_dummynode = new linkednode(0);_size = 0;}int get(int index) {if ((index+1)>_size)return -1;linkednode * cur = _dummynode;while (index--){cur = cur->next;}return cur->next->val;}void addAtHead(int val) {linkednode * newnode = new linkednode(val);newnode->next = _dummynode->next;_dummynode->next = newnode;_size++;}void addAtTail(int val) {linkednode * newnode = new linkednode(val);linkednode * cur = _dummynode;while (cur->next != NULL){cur = cur->next;}cur->next = newnode;_size++;}void addAtIndex(int index, int val) {if (index>_size)return;linkednode * newnode =  new linkednode(val);linkednode * cur = _dummynode;while (index--){cur = cur->next;}newnode->next = cur->next;cur->next = newnode;_size++;}void deleteAtIndex(int index) {if ((index+1)>_size)return ;linkednode * cur = _dummynode;while (index--){cur = cur->next;}linkednode * deletenode = cur->next;cur->next = cur->next->next;delete deletenode;_size--;}void printlinkedlist(){linkednode * cur = _dummynode;while (cur->next != NULL){cur = cur->next;cout<<cur->val<<"->";}}
};