您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

力扣算法链表篇:设计链表

在这里插入图片描述
题解:

class MyLinkedList {
public:
    //定义链表节点结构体
    struct LinkedNode{
        int val;
        LinkedNode *next;
        LinkedNode(int val):val(val),next(nullptr){}
    };
    //初始化链表
    MyLinkedList() {
        //这里定的头结点 是虚拟头结点
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }
    
    // 获取到第index个节点数值,如果index是非法数值直接返回-1,注意index是从0开始的,第0个节点就是头结点
    int get(int index) {
        if(index>(_size-1)||index<0){
            return -1;
        }
        //定位到真正的头结点
        LinkedNode *cur = _dummyHead->next;
        //如果--index 就会陷入死循环 当为0的时候 减完直接-1进入死循环
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    //在链表最前面插入一个节点,插入完成后,新插入的结点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode*newNode = new LinkedNode(val);
        newNode->next= _dummyHead->next;
        //链接到新的头结点
        _dummyHead->next = newNode;
        _size++;
    }
    
    //在链表最后添加一个节点
    void addAtTail(int val) {
        LinkedNode*newNode = new LinkedNode(val);
        LinkedNode*cur = _dummyHead;
        while(cur->next!=nullptr){
            cur = cur->next;
        }
        //插入
        cur->next = newNode;
        _size++;
    }
    
    //在第index个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度,则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度,则返回空
    void addAtIndex(int index, int val) {
        if(index>_size){
            return;
        }
        LinkedNode*newNode = new LinkedNode(val);
        LinkedNode*cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    //删除第index个节点,如果index 大于等于链表的长度,直接return,注意index是从0开始的
    void deleteAtIndex(int index) {
        if(index>=_size||index<0){
            return ;
        }
        LinkedNode*cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        LinkedNode*tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }
private:
    int _size;
    LinkedNode*_dummyHead;
};
/**
 * 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);
 */

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进