707 设计链表
dummyNode对应索引为-1,之后的节点才是真节点,索引从0开始
for循环遍历方法
i对应真节点的索引
因此i == 0时,cur = cur->next执行一次到达索引0的元素
- 遍历到指定index的元素:
for(int i = 0; i <= index; i++) - 遍历到指定index元素的前一个元素:
for(int i = 0; i < index; i++)
更好的理解方法
2025/2/9 update
可以通过调整cur指针指向的节点,控制遍历到index还是index的前一个元素:
while(index--)
while(index--)等价于for(int i = 0; i < index; i++)
class MyLinkedList {
private:
ListNode *dummyNode;
int size;
public:
MyLinkedList() {
dummyNode = new ListNode();
size = 0;
}
int get(int index) {
if(index < 0 || index >= size)
return -1;
ListNode* cur = dummyNode;
for(int i = 0; i <= index; i++){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
ListNode* newHead = new ListNode(val);
newHead->next = dummyNode->next;
dummyNode->next = newHead;
size++;
}
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
ListNode* cur = dummyNode;
while(cur->next){
cur = cur->next;
}
cur->next = newNode;
size++;
}
void addAtIndex(int index, int val) {
if(index < 0 || index > size)
return;
ListNode* cur = dummyNode;
for(int i = 0; i < index; i++){
cur = cur->next;
}
ListNode* newNode = new ListNode(val,cur->next);
cur->next = newNode;
size++;
}
void deleteAtIndex(int index) {
if(index < 0 || index >= size)
return;
ListNode* cur = dummyNode;
for(int i = 0; i < index; i++){
cur = cur->next;
}
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
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);
*/
时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
空间复杂度: O(n)