刷题了：203.移除链表元素|707.设计链表|206.反转链表

学习记录，主要参考：代码随想录

链表理论基础

什么是链表？
链表（Linked List）是一种常见的数据结构，它通过一系列的节点（Node）来存储数据元素。每个节点包含两个部分：一部分是存储数据元素的数据域（Data Field），另一部分是存储指向列表中下一个节点的指针（或引用）的指针域（Pointer Field）。链表中的节点通过指针相互连接，形成一条数据链。

链表有几种常见的类型：

• 单向链表（Single Linked List）：每个节点只包含一个指向下一个节点的指针。
  

• 双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。这使得双向链表在向前和向后遍历时都非常高效。
  

• 循环链表（Circular Linked List）：在单向或双向链表的基础上，最后一个节点的指针指向链表的头节点，形成一个环状结构。
  

链表的存储方式
表在内存中可不是连续分布的
操作与性能

• 插入与删除：在链表中插入或删除节点通常只需要改变相邻节点的指针，不需要移动其他元素，这使得这些操作相对快速。
• 遍历：链表的遍历需要从头节点开始，依次沿着指针访问链表中的每个节点。遍历方式有循环遍历和递归遍历两种。
• 随机访问：与数组不同，链表的随机访问效率较低，因为需要从头节点开始遍历到指定位置。

203.移除链表元素

题目链接:203. 移除链表元素 - 力扣（LeetCode）
文章讲解:代码随想录 (programmercarl.com)
视频讲解:手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili

cur->next->val :注意操作
ListNode* dumy_head= new ListNode(0);
使用一个哑节点（dummy node）作为链表的头部是一个常见的技巧。这行代码
ListNode* dumy_head = new ListNode(0); 就是在创建一个这样的哑节点。

/*
 * @lc app=leetcode.cn id=203 lang=cpp
 *
 * [203] 移除链表元素
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dumy_head= new ListNode(0);
        dumy_head->next = head;
        ListNode* cur = dumy_head;
        while(cur->next != NULL )
        {
            if(cur->next->val  == val){
                ListNode* tmp =  cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }
        head = dumy_head->next;
        delete dumy_head;
        return  head;

    }
};
// @lc code=end

707.设计链表

题目链接:707. 设计链表 - 力扣（LeetCode）
文章讲解:代码随想录 (programmercarl.com)
视频讲解:帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili

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

• LinkedNode(int val)
  : 这是LinkedNode类的构造函数，它接受一个整型参数val，这个参数将用于初始化新创建的链表节点的值。
• : val(val), next(nullptr)
  : 这是初始化列表，用于在构造函数体执行之前初始化类的成员变量。在这个例子中，它有两个作用：
• val(val): 第一个val是成员变量的名称，第二个val是构造函数参数的名称。这里将成员变量val初始化为构造函数参数val的值。这表示新创建的链表节点的值将等于传递给构造函数的值。
• next(nullptr): 将成员变量next初始化为nullptr。nullptr是C++11及以后版本中引入的，用于表示空指针的常量。这表示新创建的链表节点最初不指向任何其他节点。
• {}
  : 这是构造函数的函数体，由于所有初始化工作都已经在初始化列表中完成，所以这里是空的。

class MyLinkedList {

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

    MyLinkedList() {
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }

    int get(int index) { //_size = 1; 才能正确执行,后面忘记_size++ 才报错的
        if (index >= 0 && index <= (_size - 1)) { // 判断节点索引合法性
            LinkedNode* cur = _dummyHead->next;
            while (index--) {
                cur = cur->next;
            }
            return cur->val;
        } else {
            return -1;
        }
    }

   

    void addAtHead(int val) {
        LinkedNode* cur = _dummyHead;              // 指向虚节点
        LinkedNode* newnode = new LinkedNode(val); // 新建一个节点
        newnode->next = _dummyHead->next;          // 将新节点放在头部
        cur->next = newnode; // 将虚节点指向头部节点
        _size++;             // 添加节点，记得_size++
    }

    void addAtTail(int val) {
        LinkedNode* cur = _dummyHead;              // 指向虚节点
        LinkedNode* newnode = new LinkedNode(val); // 新建一个节点
        while (cur->next != nullptr) {             // 找到最后一个节点
            cur = cur->next;
        }
        cur->next = newnode; // 尾部追加
        _size++;             // 添加节点，记得_size++
    }

    // 切记index=0，是第一个有效节点，也就是虚节点后的节点
    void addAtIndex(int index, int val) {
        //     if(index > _size) return;
        //     if(index < 0) index = 0;
        if (index > _size)
            return;
        if (index < 0)
            index = 0;
        // if (index < 0 || index > (_size - 1)) { // 不符合范围

        LinkedNode* cur = _dummyHead;              // 指向虚节点
        LinkedNode* newnode = new LinkedNode(val); // 新建一个节点
        while (index--) { // 找到需要插入位置的前一个节点
            cur = cur->next;
        }
        newnode->next = cur->next; // 先记录好新节点后面需要连接的数据
        cur->next = newnode;       // 将新节点插入指定位置
        _size++;                   // 记得添加！！！
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index > (_size - 1)) { // 不符合范围
            return;

        } else {
            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);
 */

206.反转链表

题目链接:206. 反转链表 - 力扣（LeetCode）
文章讲解:代码随想录 (programmercarl.com)
视频讲解:帮你把链表操作学个通透！LeetCode：707.设计链表_哔哩哔哩_bilibili
使用双指针解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre= nullptr;
        while(cur!=nullptr){
            ListNode* tmp = cur->next;//记录还没有翻转的数据
            cur->next= pre;//进行翻转
            pre = cur;//指针玩后移动，首先移动pre
            cur = tmp;//指针玩后移动，后面移动cur
        }
        return pre;


    }
};

总结：

链表理论基础
链表不是连续存放的，通过指针连接数据

203.移除链表元素
理解虚头节点如何使用

707.设计链表
注意链表结构体如何定义，有哪些常用操作

206.反转链表
先熟悉双指针操作，查看递归的方式