526互联

Day3 链表的一些基本练习

发布时间 2023-10-17 20:42:25作者: Fancele

Day3 链表的基础练习

最基本的删除节点 Lc203 
我习惯的还是弄一个新的dummyhead，然后如果是要找的节点，就删除，删除完记得delete。

//代码没什么好看的，主要就是熟悉链表的写法
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummyHead= new ListNode(0);
        dummyHead->next=head;
        ListNode *cur =dummyHead;
        while(cur->next!= NULL){
            if(cur->next->val == val){
                ListNode *temp=cur ->next;
                cur->next=cur->next->next;
                delete temp;
            }else {
                cur=cur->next;
            }
        }
        head=dummyHead->next;
        delete dummyHead;
        return head;
    }
};

链表的基础操作练习Lc 707
没什么好说的 唯手熟尔

class MyLinkedList {
public:
struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };
    MyLinkedList() {
        _dummyHead=new LinkedNode(0);
        _size=0;
    }
    
    int get(int index) {
        if(index>(_size-1)||index<0){
            return -1;
        }
        LinkedNode *cur=_dummyHead->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    //头插法
    void addAtHead(int val) {
        LinkedNode* newNode= new LinkedNode(val);
        newNode->next=_dummyHead->next;
        _dummyHead->next=newNode;
        _size++;
    }
    //尾插法
    void addAtTail(int val) {
        LinkedNode* newNode= new LinkedNode(val);
        LinkedNode* cur=_dummyHead;
        while(cur->next){
            cur=cur->next;
        }
        cur->next=newNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index>_size) return;
        if(index<0) index=0;
        LinkedNode *newNode=new LinkedNode(val);
        LinkedNode *cur=_dummyHead;
        while(index--){
            cur=cur->next;
        }
        newNode->next=cur->next;
        cur->next=newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= _size || index <0 ){
            return;
        }
        LinkedNode *cur=_dummyHead;
        while(index--){
            cur=cur->next;
        }
        LinkedNode *temp=cur->next;
        cur->next=temp->next;
        delete temp;
        temp=nullptr;//防止temp变成野指针
        _size--;
    }
    private:
    int _size;
    LinkedNode* _dummyHead;
};

反转链表，可以好好练习一下，Lc206

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur=head;
        ListNode *pre=NULL;
        ListNode *temp;
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};
//递归的写法可以对照下面的双指针写法，然后一一对应就行了
class Solution {
public:
    ListNode* reverse(ListNode*pre,ListNode* cur){
        if(cur==NULL) return pre;
        ListNode *temp;
        temp=cur->next;
        cur->next=pre;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head){
        return reverse(NULL,head);
    }
};