链表理论基础203.移除链表元素707.设计链表206.反转链表

资料来源：代码随想录 (programmercarl.com)

1 链表理论基础

定义：是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

1.1链表类型

单链表

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

循环链表

就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

1.2 链表存储

指针、地址存储，不连续；使用指针索引

1.3 链表代码定义格式

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

对比数组：增加、删除元素简单，但是查询很麻烦

2. 移除元素

//方法1：
	ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
//方法2：虚拟头节点
        Listnode* dummyHead = new Listnode(0);//确定val不是0
        dummyHead->next = head;
        Listnode* cur = dummyHead;
        while (cur != NULL && cur->next != NULL)
        {
            if(cur->next->val == val){
                Listnode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else{
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;

3.设计链表

class ListNodeMethod
{
public:
    // 定义链表节点结构体
    struct Listnode
    {
        /* data */
        int val;
        Listnode *next;
        Listnode(int x) : val(x), next(NULL) {}
    };
    /**
     * @brief 设计链表
     * 功能1：get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
     * 功能2：addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
     * 功能3：addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
     * 功能4：addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。
     *      如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
     * 功能5：deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
     */

    // 初始化链表
    ListNodeMethod()
    {
        _dummyHead = new Listnode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }
    // 功能1:节点从0开始
    int get(int index)
    {
        int i = 0;
        if (index > (_size - 1) || index < 0)
        {
            return -1;
        }

        Listnode *cur = _dummyHead;
        while (index--)
        {
            /* code */
            cur = cur->next;
        }

        return cur->val;
    }
    // 功能2：头插
    Listnode *addAtHead(int val)
    {
        // 自己思考版
        //  Listnode* cur = _dummyHead;
        //  Listnode* tmp = cur->next;
        //  Listnode* head = new Listnode(val);
        //  _dummyHead->next = head;
        //  head->next = tmp;
        // 标准版
        Listnode *newHead = new Listnode(val);
        newHead->next = _dummyHead->next;
        _dummyHead->next = newHead;
        _size++;
        return newHead;
    }
    // 功能3：尾插
    void addAtTail(int val)
    {
        // 自己思考版
        //  Listnode* newLast = new Listnode(val);
        //  int i =_size;
        //  Listnode* cur =_dummyHead;
        //  while(i--){
        //      cur = cur->next;
        //  }
        //  cur->next = newLast;
        // 标准版
        Listnode *newNode = new Listnode(val);
        Listnode *cur = _dummyHead;
        while (cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    void addAtIndex(int index, int val)
    {

        if (index < 0)
            index = 0;
        if (index > _size)
            return;
        Listnode *middle = new Listnode(val);
        Listnode *cur = _dummyHead;
        while (index--)
        {
            /* code */
            cur = cur->next;
        }
        middle->next = cur->next;
        cur->next = middle;
        _size++;
    }

    // 功能4：
    void deleteAtIndex(int index)
    {
        if (index < 0)
            return;
        if (index >= _size)
            return;
        Listnode *cur = _dummyHead;
        while (index--)
        {
            cur = cur->next;
        }
        Listnode *tmp = cur->next;
        cur->next = tmp->next;
        delete tmp;
        tmp = nullptr;
        _size--;
    }

private:
    int _size;
    Listnode *_dummyHead;
};

4.翻转链表

自己思考写了双指针法，但是有点小错。

两种递归法，还需要再熟悉熟悉，看得懂，但是感觉写不出来

class Solution
{
private:
    /* data */
public:
    Solution(/* args */);
    ~Solution();
    struct ListNode
    {
        /* data */
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    //双指针法
    ListNode* reverseList(ListNode* head){
        ListNode* temp;
        ListNode* cur = head;
        ListNode* pre = NULL;
        while (cur)
        {
            /* code */
            temp = cur->next;
            cur->next = pre;
            pre = cur;//自己思考时少了
            cur = temp;
        }
        return pre;      
    }
    //递归
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;

        reverse(cur, temp);

    }
    ListNode* reverseList(ListNode* head){
        reverse(NULL, head);
    }

};

总结：

单链表代码：

//定义链表
    struct ListNode
    {
        /* data */
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
//虚拟头结点
    // 初始化链表（在类中，定义在private）
    ListNodeMethod()
    {
        _dummyHead = new Listnode(0); // 这里定义的头结点 是一个虚拟头结点，而不											是真正的链表头结点
        _size = 0;
    }
	//单独定义
    Listnode *_dummyHead = new Listnode(0);

本质就是指针的熟悉使用

关于时间复杂度的区别：

数组索引可以直接找到元素O（1）；但是增删需要移动元素O（n）

链表找元素很麻烦，需要指针一步步指下去O(n)；头插尾插增删很容易，操作指针一次即可O(1)；但是中间插入需要先找到位置，指针操作和前面一样O(index)。