[数据结构与算法]《Leetcode》链表-学习

链表的分类：

1.单链表

2.双链表

3.循环链表

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

C++设计链表

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

203 移除链表元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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;
};

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