我算是知道dummyHead虚假头节点的妙处了,addAtHead的时候,不用判断链表是否为空,直接把新节点往dummyHead后面一连就可以
注意链表的长度要实时更新!
class MyLinkedList {
private:
ListNode* _dummyHead;
int _size;
public:
//创建一个空链表,把成员变量初始化一下
MyLinkedList() {
_dummyHead = new ListNode(0);
_size = 0;//链表的长度记得要实时更新!
}
int get(int index) {
if((index < 0) || (index >= _size)) return -1;
ListNode* cur = _dummyHead;
//假设索引为3,dum 0 1 2 3,要找4次,cur成为我们要的节点
for(int i = 0; i <= index; i++) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;//增加节点,链表长度更新
}
void addAtTail(int val) {
ListNode* cur = _dummyHead;
while(cur->next != nullptr) {
cur = cur->next;
}
ListNode* newNode = new ListNode(val);
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if(index > _size) return;
else if(index == _size) {
addAtTail(val); return;
}
else if(index == 0) {
addAtHead(val); return;
} else {
ListNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
ListNode* newNode = new ListNode(val);
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
}
void deleteAtIndex(int index) {
if((index < 0) || (index >= _size)) return;
ListNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
ListNode* tem = cur->next;
cur->next = cur->next->next;
delete tem;
_size--;
}
};
/**
* 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);
*/