【C++ 数据结构：链表】二刷LeetCode707设计链表

seo排名网 2023年01月31日 23:37 213 0

【C++链表】

使用c++重新写一遍LeetCode707设计链表

目的是熟悉c++中链表的操作

知识点

C++链表节点的实现

在c++中，一般通过结构体来定义链表的节点，也需要写构造函数（使用初始化列表）

如：

struct ListNode{

        int val;

        ListNode* next;

        //要写构造函数

        //结构体中的构造函数要用初始化列表来初始化属性

        ListNode(int val) :val(val), next(nullptr){}

    };

访问节点中的属性遵循结构体指针操作

即利用操作符 -> 可以通过结构体指针访问结构体属性

例如，遍历链表

		while(cur->next != nullptr){

            cur = cur->next;

        }

实现一个链表节点

c++中对于链表的操作均通过指针完成，例如：

//创建一个待插入的节点

ListNode* node4add = new ListNode(val);

上述代码在堆区开辟一块新内存存放一个ListNode对象，将指针node4add指向该区域

内存释放

在c++中操作节点，如果不再需要某个节点，一定要把该节点删除（释放内存）

例如删除节点的操作中，我们将待删除节点的上一个节点指向待删除节点的后一个节点，绕过了待删除节点，实现对该节点的删除

如果是其他语言，就直接操作就行了，在c++中不行

我们还需要将待删除节点保存下来，再删除释放

void deleteAtIndex(int index) {

        if(index < 0 || index >= m_size){

            return;

        }

        //将当前指针指向dummy

        ListNode* cur = m_dummy;

        while(index){

            cur = cur->next;

            index--;

        }

        //要先把待删除的节点用临时节点保存，以便之后进行delete操作

        //如果不删除的话会报错

        ListNode* tmp = cur->next;

        cur->next = cur->next->next;

        delete tmp;

        m_size--;

    }

完整代码

class MyLinkedList {

public:

    //要先定义一个结构体作为节点

    struct ListNode{

        int val;

        ListNode* next;

        //要写构造函数

        //结构体中的构造函数要用初始化列表来初始化属性

        ListNode(int val) :val(val), next(nullptr){}

    };

    MyLinkedList() {

        //初始化（定义/实现）链表的头节点和size

        //实际上这两个属于MyLinkedList类的成员属性，由于我们不想其被修改

        //因此可以把它们写在private区

        m_size = 0;

        m_dummy = new ListNode(0);//在堆区开辟一块新内存存放一个ListNode对象，将指针m_dummy指向该区域

    }

    int get(int index) {

        if (index > (m_size - 1) || index < 0) {

            return -1;

        }

        //将当前指针指向头节点（即dummy的下一个）

        // ListNode* cur = m_dummy->next;

        ListNode* cur = m_dummy;

        while(index){

            cur = cur->next;

            index--;

        }

        return cur->next->val;//记得返回的是cur的下一个节点，因为最初cur指向的是dummy

        //要么一开始就让cur指向dummy->next

    }

    void addAtHead(int val) {

        //创建一个待插入的节点

        ListNode* node4add = new ListNode(val);

        node4add->next = m_dummy->next;

        m_dummy->next = node4add;

        m_size++;

    }

    void addAtTail(int val) {

        //创建一个待插入的节点

        ListNode* node4add = new ListNode(val);

        ListNode* cur = m_dummy;

        //遍历到链表末尾处

        while(cur->next != nullptr){

            cur = cur->next;

        }

        //插入新节点

        cur->next = node4add;

        m_size++;

    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。

    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点

    // 如果index大于链表的长度，则返回空

    // 如果index小于0，则在头部插入节点

    void addAtIndex(int index, int val) {

        if(index > m_size){

            return;

        }else if(index < 0){

            index = 0;

        }

        //将当前指针指向dummy

        ListNode* cur = m_dummy;

        //遍历到index位置

        while(index){

            cur = cur->next;

            index--;

        }

        //找到插入位置之后开始插入

        //创建一个待插入的节点

        ListNode* node4add = new ListNode(val);

        node4add->next = cur->next;

        cur->next = node4add;

        //链表长度增加

        m_size++;

    }

    void deleteAtIndex(int index) {

        if(index < 0 || index >= m_size){

            return;

        }

        //将当前指针指向dummy

        ListNode* cur = m_dummy;

        while(index){

            cur = cur->next;

            index--;

        }

        //要先把待删除的节点用临时节点保存，以便之后进行delete操作

        //如果不删除的话会报错

        ListNode* tmp = cur->next;

        cur->next = cur->next->next;

        delete tmp;

        m_size--;

    }

private:

    int m_size;//声明链表长度

    ListNode* m_dummy;//声明dummy头节点

};

/**

 * 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);

 */

707二刷错误点

1、忘记处理链表size

记得定义链表长度size

2、next的含义

举个例子

 void addAtIndex(int index, int val) {

        if(index > m_size){

            return;

        }else if(index < 0){

            index = 0;

        }

        //将当前指针指向dummy

        ListNode* cur = m_dummy;

        //遍历到index位置

        while(index){

            cur = cur->next;

            index--;

        }

        //找到插入位置之后开始插入

        //创建一个待插入的节点

        ListNode* node4add = new ListNode(val);

        node4add->next = cur->next;

        cur->next = node4add;

        //链表长度增加

        m_size++;

    }