链表理论基础；

资料来源：代码随想录 (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;