设计链表 双链表 - lifengyu360/lifengyu_first_git_test GitHub Wiki

class MyLinkedList {

public:

//定义链表节点结构体

struct LinkedNode
{
    int val;
    LinkedNode *next;
    LinkedNode(int val):val(val),next(nullptr){}
};

//初始化链表
MyLinkedList() {
    m_dummyHead=new LinkedNode(0);
    m_size=0;
}


//获取到第index个节点数值，如果index是非法数值直接返回-1，注意index是从0开始的，第0个节点就是头结点
int get(int index) {
    if(index>m_size-1||index<0)
    {
        return -1;
    }
    LinkedNode *cur=m_dummyHead->next;
    while(index--)//注意--index会陷入死循环
    {
        cur=cur->next;
    }
    return cur->val;
}
//在链表最前面插入一个结点，插入完成后，新插入的结点为链表的新的头结点
void addAtHead(int val) {
    LinkedNode *newNode=new LinkedNode(val);
    LinkedNode *cur=m_dummyHead;
    newNode->next=cur->next;
    cur->next=newNode;
    m_size++;//注意++
}
//在链表最后面添加一个结点
void addAtTail(int val) {
    LinkedNode *newNode=new LinkedNode(val);
    LinkedNode *cur=m_dummyHead;
    while(cur->next!=NULL)
    {
        cur=cur->next;
    }
    cur->next=newNode;
    m_size++;//注意++
}
//在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头结点
//如果index等于链表的长度，则说明是新插入和结点为链表的尾结点
//如果index大于链表的长度，则返回空
void addAtIndex(int index, int val) {
    if(index>m_size)
    {
        return;
    }
    LinkedNode *newNode=new LinkedNode(val);
    LinkedNode *cur=m_dummyHead;
    while(index--)
    {
        cur=cur->next;
    }
    newNode->next=cur->next;
    cur->next=newNode;
    m_size++;//注意++
}
//删除第index个节点，如果index大于等于链表的长度，直接return，注意index是从0开始的
void deleteAtIndex(int index) {
    if(index>=m_size||index<0)
    {
        return;
    }
    LinkedNode *cur=m_dummyHead;
    while(index--)
    {
        cur=cur->next;
    }
    LinkedNode *tmp=cur->next;
    cur->next=cur->next->next;
    delete tmp;
    m_size--;//注意--
}
private:
int m_size;
LinkedNode *m_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); */