跳转至

707 设计链表

leetcode

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的前一个元素:

ListNode* cur = dummyNode->next;
while(index--){
    cur = cur->next;
}
ListNode* cur = dummyNode;
while(index--){
    cur = cur->next;
}
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)