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

LeetCode 203.移除链表元素

视频链接: LeetCode203

思路: 根据链表的性质，将目标值对应的节点保存在一个临时节点中，再重新设置cur下一个节点，再将临时节点进行删除

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //删除头节点
        while(head != NULL && head->val == val){
            ListNode * temp=head;
            head=head->next;
            delete temp;
        }
        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;
    }
};

LeetCode 707.设计链表

视频链接: LeetCode707

思路: 注释

class MyLinkedList {
private:
    struct Listnode{//定义链表结点结构体
        int val;//结点的值val
        Listnode* next;//结点的指针域next,指向下一个结点
        //三个Listnode构造函数
        Listnode():val(0),next(nullptr){}//参数为空
        Listnode(int v):val(v),next(nullptr){}//一个参数
        Listnode(int v,Listnode* n):val(v),next(n){}//两个参数
    };
    int len;//链表长度
    Listnode* dummyhead;//链表虚拟头结点
public:
    MyLinkedList() {//MyLinkedList构造函数
        len=0;//链表长度初始化为0
        dummyhead=new Listnode();//创建链表虚拟头结点
    }
    
    int get(int index) {//获取链表中第index个节点的值
        if(index<0||index>len-1) return -1;//索引无效返回-1
        Listnode* head=dummyhead->next;//dummyhead是虚拟头结点,而dummyhead->next是头结点
        while(index--) head=head->next;//找到第index个链表结点
        return head->val;//返回第index个链表结点的值val
    }
    
    void addAtHead(int val) {//在链表的第一个元素之前添加一个值为val的节点
        if(val<0||val>1000) return;//val值无效，直接返回
        Listnode* n=new Listnode(val);//新建值为val的链表结点n
        n->next=dummyhead->next;//将新链表结点n插入头结点前,新结点的指针域next为头结点指针,即新结点n的next指针指向头结点
        dummyhead->next=n;//虚拟头结点指针域next为新结点指针n,即虚拟头结点的next指针指向新结点n
        len++;//链表长度加一
    }
    
    void addAtTail(int val) {//将值为val的节点追加到链表的最后一个元素
        if(val<0||val>1000) return;//val值无效，直接返回
        Listnode* n=new Listnode(val),*cur=dummyhead;//新建值为val的链表结点n和当前结点指针变量cur
        while(cur->next) cur=cur->next;//通过cur找到链表中最后一个结点
        cur->next=n;//将新结点n插入链表末尾,即最后一个结点的指针域为新结点指针n
        len++;//链表长度加一
    }
    
    void addAtIndex(int index, int val) {//在链表中的第index个节点之前添加值为val的节点
        if(val<0||val>1000||index>len) return;//val值或index值无效，直接返回
        if(index<=0) addAtHead(val);//index<=0时,在头部插入值为val的新结点
        else if(index==len) addAtTail(val);//index=len时,在尾部插入值为val的新结点
        else{
            Listnode* n=new Listnode(val),*cur=dummyhead;//新建值为val的链表结点n和当前结点指针变量cur
            while(index--) cur=cur->next;//找到第index-1个链表结点
            n->next=cur->next;//将新链表结点n插入第index个链表结点前,新结点的指针域next为第index个链表结点的指针域next,即新结点n的next指针指向第index个链表结点
            cur->next=n;//第index个链表结点的指针域next为新结点指针n,即第index个链表结点的next指针指向新结点n
            len++;//链表长度加一
        }
    }
    
    void deleteAtIndex(int index) {//删除链表中的第index个节点
        if(index<0||index>len-1) return;//index值无效，直接返回
        Listnode* cur=dummyhead,*t=nullptr;//当前结点指针变量cur和临时结点t
        while(index--) cur=cur->next;//找到第index-1个结点
        t=cur->next;//t保存要删除的第index个结点
        cur->next=t->next;//第index-1个结点的指针域next为第index个结点的指针域next,即删除第index个结点
        delete t;//释放第index个结点的空间
        len--;//链表长度减一
    }
};

LeetCode 206.反转链表

视频链接: LeetCode206

思路: 

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev=nullptr;
        ListNode*curr=head;
        while(curr){
            ListNode* next=curr->next;
            curr->next=prev;
            prev=curr;
            curr=next;
        }
        return prev;
    }
};