代码随想录算法训练营day3 | 203.移除链表元素 707.设计链表 206.反转链表

链表理论基础

单链表

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（指向下一个节点），最后一个指针域指向NULL（空节点）。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

链表的存储方式

链表不是像指针一样在内存中是连续分布的，是散落分布的，分配机制取决于操作系统的内存管理。

循环链表

循环链表，顾名思义，就是链表首尾相连。

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

性能分析

	插入/删除（时间复杂度	查询（时间复杂度）	适用场景
数组	O(n)	O(1)	数据量固定，频繁查找，较少增删
链表	O(1)	O(n)	数据量不定，较少查找，频繁增删

刷题笔记day3

203.移除链表元素

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

while (temp != NULL && temp->val == val)

temp != NULL应该放在前面，不然NULL->val会报错。
一定要delete掉要删除的节点。
在原链表进行删除需要两个while循环，但是如果造一个虚拟头节点可以只需要一次while循环。
动态分配的内存指针同样要用动态分配的内存指针才能去赋值。

自己写的代码

看了题解后用虚拟头节点法写的代码：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == NULL) {
            return NULL;
        }
        ListNode* virhead = new ListNode(0);
        virhead->next = head;
        ListNode* cur = virhead;
        while (cur->next != NULL) {
            if (cur->next->val == val) {
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }
            else {
                cur = cur->next;
            }
        }
        return virhead->next;
    }
};

看了题解后的收获

在原链表进行删除需要两个while循环，但是如果造一个虚拟头节点可以只需要一次while循环。
动态分配的内存指针同样要用动态分配的内存指针才能去赋值。

707.设计链表

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

选择了直接用原链表进行操作，碰到了很多坑。主要是_size在计算过程中的错误。按题意，new了一个之后_size=0，但是实际已经=1，所以导致添加元素删减元素时都要加上一些条件判断。

自己写的代码

研究了大概一个多小时写出来的代码：

class MyLinkedList {
public:
    MyLinkedList() {
        _head = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index > _size - 1) {
            return -1;
        }
        LinkedNode* cur = _head;
        if (index == 0) {
            return cur->val;
        }
        else {
            for (int i = 1; i <= index; ++i) {
                cur = cur->next;
            }
        }
        return cur->val;
    }

    void addAtHead(int val) {
        LinkedNode* newhead = new LinkedNode(val);
        if (_size == 0) {
            _head = newhead;
        }
        else {
            newhead->next = _head;
            _head = newhead;
        }
        ++_size;
    }
    
    void addAtTail(int val) {
        LinkedNode* newtail = new LinkedNode(val);
        if (_size == 0) {
            _head = newtail;
        }
        else {
            LinkedNode* cur = _head;
            while (cur->next != NULL) {
                cur = cur->next;
            }
            cur->next = newtail;
        }
        ++_size;
    }
    
    void addAtIndex(int index, int val) {
        if (index > _size || index < 0) {
            return;
        }
        if (index == 0) {
            addAtHead(val);
        }
        else {
            int counts = 0;
            LinkedNode* cur = _head;
            while (cur->next != NULL)
            {
                ++counts;
                if (counts == index) {
                    LinkedNode* newnode = new LinkedNode(val);
                    newnode->next = cur->next;
                    cur->next = newnode;
                    ++_size;
                    return;
                }
                cur = cur->next;
            }
            if (index == counts + 1) {
                addAtTail(val);
            }
            if (index > counts + 1) {
                return;
            }
        }

    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index > _size - 1)
        {
            return;
        }
        if (index == 0) {
            LinkedNode* temp = _head;
            _head = _head->next;
            delete temp;
        }
        else {
            LinkedNode* cur = _head;
            int counts = 0;
            while (cur->next != NULL) {
                ++counts;
                if (counts == index) {
                    LinkedNode* temp = cur->next;
                    cur->next = cur->next->next; 
                    break;
                }
                cur = cur->next;
            }
        }
        --_size;
    }

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

看了题解后的收获

看了题解后自己手撕了一遍用虚拟头节点的版本：

class MyLinkedList {
public:
    MyLinkedList() {
        _dummyhead = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if (index > _size - 1 || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyhead->next;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* node = new LinkedNode(val);
        node->next = _dummyhead->next;
        _dummyhead->next = node;
        ++_size;
    }
    
    void addAtTail(int val) {
        LinkedNode* cur = new LinkedNode(val);
        LinkedNode* temp = _dummyhead;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = cur;
        ++_size;
    }
    
    void addAtIndex(int index, int val) {
        if (index > _size|| index < 0) {
            return;
        }
        LinkedNode* cur = new LinkedNode(val);
        LinkedNode* temp = _dummyhead;
        while (index--) {
            temp = temp->next;
        }
        cur->next = temp->next;
        temp->next = cur;
        ++_size;
    }
    
    void deleteAtIndex(int index) {
        if (index > _size - 1 || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyhead;
        while (index--) {
            cur = cur->next;
        }
        LinkedNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        --_size;
    }

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

如果使用虚拟头节点真的简单很多！主要是更容易符合题意。如果题意new后的初始_size = 1，那应该会简单很多。

206.反转链表

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

循环条件应该是：while (temp->next != NULL)
循环条件有问题。

看了题解后的收获

掌握了本题的双指针解法。