[数据结构与算法]代码随想录算法训练营三期 day 03 - 链表(1)

链表理论基础

原文链接：关于链表，你该了解这些！
定义：链表是一种用指针串联起来的数据结构，每个结点由两部分组成，数据域 $val$ 和 指针域 $next$。最后一个结点的指针域为 $null$。

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x): val(x), next(NULL) {};
};

类型：单链表、双链表（每个结点有两个指针域）、循环链表（首尾相接）
存储方式：通过指针链接，内存地址不是连续的。
操作：
(1) 删除结点：

(1) 插入结点：

链表的插入和删除操作都是 $O(1)$ 的复杂度，而且也不会影响其他结点。
但是对于单链表来说，删除最后一个结点，需要从头节点找到倒数第 $2$ 个结点的 $next$ 指针进行操作，复杂度是 $O(n)$。
链表和数组对比:

203. 移除链表元素

原文链接：203. 移除链表元素
题目链接：203. 移除链表元素
视频链接：链表基础操作| LeetCode：203.移除链表元素
学习记录：
(1) 不添加虚拟头节点：
删除 头结点 与 删除 其他结点 操作方式不一致：
i. 删除头结点：$head=head\to next;$（注意要使用 $while$)
ii. 删除其他结点: $cur\to next=cur\to next\to next;$
代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head -> val == val) {
            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) 添加虚拟头节点：
删除头结点与删除其他结点方式一致：

注意最后要返回的是 $res=dummyHead\to next;$

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

707. 设计链表

原文链接：707. 设计链表
题目链接：707. 设计链表
视频链接：帮你把链表操作学个通透！LeetCode：707. 设计链表
学习记录：
(1) 获取第 $index$ 个结点的数值：
因为要找的是 第 $index$ 个结点， 所以 $cur=dummyHead\to next;$

    int get(int index) {
        if (index >= size || index < 0) {
            return -1;
        }
        Node* cur = dummyHead -> next;
        while (index--) {
            cur = cur -> next;
        }
        return cur -> val;
    }

(2) 头插:
i. $newNode\to next=dummyHead\to next;$
ii. $dummyHead\to next=newNode;$
iii. $size++;$

    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode -> next = dummyHead -> next;
        dummyHead -> next = newNode;
        size++;
    } 

(3) 尾插
因为要找的是最后一个结点，所以 $cur=dummyHead;$
找到最后一个结点后, $cur\to next=newnode;$ $size++;$

    void addAtTail(int val) {
        Node* newNode = new Node(val);
        Node* cur = dummyHead;
        while (cur -> next != NULL) {
            cur = cur -> next;
        }
        cur -> next = newNode;
        size++;
    }

(4) 普通插入
因为要找到第 $index$ 个结点的前一个结点，所以 $cur=dummyHead;$
与头插类似：
i. $newNode\to next=cur\to next;$
ii. $cur\to next=newNode;$
iii. $size++$;

    void addAtIndex(int index, int val) {
        if (index > size || index < 0) {
            return ;
        }
        Node* newNode = new Node(val);
        Node* cur = dummyHead;
        while (index--) {
            cur = cur -> next;
        }
        newNode -> next = cur -> next;
        cur -> next = newNode;
        size++;
    }

(5) 删除
因为要找到第 $index$ 个结点的前一个结点，所以 $cur=dummyHead;$
i. $cur\to next=cur\to next\to next;$
ii. $size??;$

    void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        Node* cur = dummyHead;
        while (index--) {
            cur = cur -> next;
        }
        Node* tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete tmp;
        size--;
    }

每次插入或删除操作都要记得更新 $size$ !
总代码：

class MyLinkedList {
public:
    struct Node {
        int val;
        Node* next;
        Node(int val): val(val), next(NULL) {}
    };
    MyLinkedList() {
        dummyNode = new Node(0);
        size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        Node* cur = dummyNode -> next;
        while (index--) {
            cur = cur -> next;
        }
        return cur -> val;
    }
    
    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode -> next = dummyNode -> next;
        dummyNode -> next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        Node* newNode = new Node(val);
        Node* cur = dummyNode;
        while (cur -> next != NULL) {
            cur = cur -> next;
        }
        cur -> next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        Node* newNode = new Node(val);
        Node *cur = dummyNode;
        while (index--) {
            cur = cur -> next;
        }
        newNode -> next = cur -> next;
        cur -> next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        Node *cur = dummyNode;
        while (index--) {
            cur = cur -> next;
        }
        Node *tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete tmp;
        size--;
    }
private:
    Node* dummyNode;
    int size;
};

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

学习时长: 1.5 hours