《Leetcode》链表-学习

链表的分类：

1.单链表

2.双链表

3.循环链表

链表的存储是根据操作系统的内存管理分配的。

C++设计链表

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

203 移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //删除头节点
        while (head != NULL && head->val == val){//NULL大写
            ListNode* tmp = head;//负责清理内存空间
            head = head->next;
            delete tmp;
        }

        //删除子节点
        ListNode* cur = head;//传进来的是头节点位置,直接使用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;
    }
};

707. 设计链表

class MylinkedList {
public:
    struct linkedNode{//命名
        int val;
        linkedNode* next;
        linkedNode(int x):val(x), next(nullptr){}//别忘了：
    };

    MylinkedList() {//初始化
        dhead = new linkedNode(0);//new一个对象
        len = 0;
    }
    
    int get(int index) {
        if (index > (len - 1) || index < 0) {
            return -1;
        }
        linkedNode* cur = dhead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        linkedNode*newnode = new linkedNode(val);
        newnode->next = dhead->next;
        dhead->next = newnode;
        len++;
    }
    
    void addAtTail(int val) {
        linkedNode*newnode = new linkedNode(val);
        linkedNode*cur = dhead;
        while (cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newnode;
        len++;
    }
    
    void addAtIndex(int index, int val) {
        if (len < index) {
            return;
        }
        linkedNode*newnode = new linkedNode(val);
        linkedNode*cur = dhead;
        while (index--){
            cur = cur->next;
        }
        newnode->next = cur->next;
        cur->next = newnode;
        len++;
    }
    
    void deleteAtIndex(int index) {
        if (len <= index  || index < 0 ) {
            return;
        }
        linkedNode*cur = dhead;
        while (index--){
            cur = cur->next;
        }
        linkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        len--;
    }

    // 打印链表
    void printlinkedList() {
        linkedNode* cur = dhead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

private://设定虚拟头节点
    linkedNode* dhead;
    int len;
};