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

/**
 * 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* dummy_head = new ListNode(0);//生成一个虚拟头节点
        dummy_head->next = head; //将头节点和链表连起来
        ListNode* curr = dummy_head; //用于遍历链表的指针
        while(curr->next!=nullptr){
            if(curr->next->val == val){
                ListNode* temp_node = curr->next;
                curr->next = curr->next->next;
                delete temp_node;//释放内存
                temp_node = nullptr;
            }else{
                curr = curr->next;
            }
        }
        //因为存在链表头节点被删的可能,如果被删除,不做如下操作而直接返回head则链表地址会指向一个未分配内存的位置,会报错.所以需要重新赋值头节点.
        head = dummy_head->next;//
        return head;
    }
};

class MyLinkedList {
public:
    struct LInkedNode{
        int val;
        LInkedNode* next;
        LInkedNode(int val):val(val),next(nullptr){
        }
    };
    MyLinkedList():size_(0),dummy_head_(new LInkedNode(0)){
    }
    int get(int index) {
       if(index > size_ - 1||index < 0){
           return -1;
       }
       LInkedNode* curr = dummy_head_->next;
       while(index -- ){
           curr = curr->next;
       }
       int val = curr->val;
       return val;
    }
    void addAtHead(int val) {
       LInkedNode* curr = new LInkedNode(val);
       curr->next = dummy_head_->next;
       dummy_head_->next = curr;
       ++size_;
    }
    void addAtTail(int val) {
        LInkedNode* curr = dummy_head_;
        while(curr->next!=nullptr){
            curr = curr->next;
        }
        curr->next = new LInkedNode(val);
        ++size_;
    }
    void addAtIndex(int index, int val) {
        if(index >size_ )return;
        if(index < 0 )index = 0;
        LInkedNode* curr = dummy_head_;
        while(index--){
            curr = curr->next;
        }
        LInkedNode* tmp = curr->next;
        curr->next = new LInkedNode(val);
        curr->next->next = tmp;      
        ++size_;
    }
    void deleteAtIndex(int index) {
       if(index >=size_||index < 0)return;
       LInkedNode* curr = dummy_head_;
       while(index --){
           curr = curr->next;
       }
       LInkedNode* tmp = curr->next;
       curr->next = curr->next->next;
       delete tmp;
       tmp = nullptr;
       size_--;
    }
private:
int size_;
LInkedNode* dummy_head_;
};
/**
 * 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);
 */

/**
 * 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 = nullptr;
        ListNode* curr = head;
        while(curr!=nullptr){
        ListNode* tmp = curr->next;
        curr->next = pre;
        pre =curr;
        curr  = tmp;
        }
        return pre;
    }
};

/**
 * 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* reverse(ListNode* pre,ListNode*curr){
        if(curr==nullptr)return pre;
        ListNode* tmp = curr->next;
        curr->next = pre;
        // pre = curr;
        // curr=tmp;
        return reverse(curr,tmp);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr,head);
    }
};