代码随想录算法训练营第三天|LeetCode203，707，206

LeetCode 203 移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

//区分了删除头结点元素和删除非头结点元素
/**
 * 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) {
        //删除头结点元素
        //注意不能用if，如果前面的结点元素都和val相等只能删掉一个
        //if(head != NULL && head->val == val){
        while(head != NULL && head->val == val){
            ListNode *tmp = head;
            head = head->next;
            delete tmp;
        }
        //删除非头结点元素
        ListNode *ptr = head;
        while(ptr != NULL && ptr->next != NULL){
            if(ptr->next->val == val){
                ListNode *tmp = ptr->next;
                ptr->next = ptr->next->next;
                delete tmp;
            }
            else{
                ptr = ptr->next;
            }
        }
        return head;

    }
};

//使用虚拟头结点遍历，就无需区分头结点和非头结点
/**
 * 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) {
        //设置一个虚拟头结点，并将其初始化
        ListNode *virtualNode = new ListNode(0);
        virtualNode->next = head;
        ListNode *virtualHead = virtualNode;
        //循环判断
        while(virtualNode->next != NULL){
            if(virtualNode->next->val == val){
                ListNode *tmp = virtualNode->next;
                virtualNode->next = virtualNode->next->next;
                delete tmp;
            }
            else{
                virtualNode = virtualNode->next;
            }
        }
        return virtualHead->next;

    }
};

视频讲解链接：https://www.bilibili.com/video/BV18B4y1s7R9/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0203.移除链表元素.html#其他语言版本

LeetCode 707 设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/description/

class MyLinkedList {
public:

    struct ListNode{
        int _val; //该节点存储的值
        ListNode *_next; //指向下一个节点的指针
        //节点构造函数
        ListNode (int val)
        :_val(val)
        ,_next(nullptr)
        {
            //cout << "ListNode(int)" << endl;
        }
    };

    //初始化链表
    MyLinkedList() {
        //ListNode _virtualHead(0);
        _virtualHead = new ListNode(0); //初始化一个虚拟头结点
        _size = 0; //链表初始长度为0

    }
    
    int get(int index) {
        //边界判断
        if((index > _size - 1) || index < 0){
           return -1;
        }
        ListNode *ptr = _virtualHead;
        for(int i = 0; i <= index; i++){
            ptr = ptr->_next;
        }
        return ptr->_val;
    }
    
    void addAtHead(int val) {
        ListNode *newNode = new ListNode(val);
        newNode->_next = _virtualHead->_next;
        _virtualHead->_next = newNode;
        _size++;
        //cout <<  _virtualHead->_next->_val;
    }
    
    void addAtTail(int val) {
        ListNode *newNode = new ListNode(val);
        ListNode *ptr = _virtualHead;
        while(ptr->_next != NULL) ptr = ptr->_next;
        ptr->_next = newNode;
        _size++;

    }
    
    void addAtIndex(int index, int val) {
        if(index < _size && index > 0){
            ListNode *ptr = _virtualHead;
            for(int i = 0; i < index; i++) ptr = ptr->_next;
            ListNode *newNode = new ListNode(val);
            newNode->_next = ptr->_next;
            ptr->_next = newNode;
            _size++;
        }
        else if(index <= 0){
            addAtHead(val);
        }
        else if(index == _size){
            addAtTail(val);
        }

    }
    
    void deleteAtIndex(int index) {
        if(index < _size && index >= 0){
            ListNode *ptr = _virtualHead;
            for(int i = 0; i < index; i++) ptr = ptr->_next;
            ListNode *tmp = ptr->_next;
            ptr->_next = tmp->_next;
            delete tmp;
	        --_size;
        }

    }
    
    // 打印链表
    void printLinkedList() {
        ListNode* ptr = _virtualHead;
        while (ptr->_next != nullptr) {
            cout << ptr->_next->_val << " ";
            ptr = ptr->_next;
        }
        cout << endl;
    }

    //数据成员
    private:
    ListNode *_virtualHead;
    int _size;
};

视频讲解链接：https://www.bilibili.com/video/BV1FU4y1X7WD/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0707.设计链表.html#代码

LeetCode 206 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

/**
 * 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* reverseList(ListNode* head) {
        //利用双指针
        ListNode *pre = NULL;
        ListNode *ptr = head;
        //利用tmp保存下一个节点
        ListNode *tmp;
        while(ptr){
            tmp = ptr->next; //保存下一个节点
            ptr->next = pre; //进行翻转操作
            pre = ptr;
            ptr = tmp;
        }
        return pre;
    }
};

视频讲解链接：https://www.bilibili.com/video/BV1nB4y1i7eL/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0206.翻转链表.html#双指针法