当前位置：首页 > news >正文

day3 203移除链表元素 707设计链表 206反转链表

news 来源：原创 2024/11/17 21:44:51

203 移除链表元素

定义一个虚拟头节点
这样子可以不用分开处理头结点
统一了写法
思路就是找到cur -> next -> val，借助前一个节点，直接连接到后一个

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //new一个新指针
        //如果一开始不知道指针本身指向哪里，就要做初始化，否则成了野指针
        ListNode* dummyhead = new ListNode(0);
        //定义一个新指针，本身就指向了dummyhead
        ListNode* cur = dummyhead;//从dummyhead开始，不漏掉head
        dummyhead -> next = head;
        while(cur -> next != NULL) {
            if(cur -> next -> val == val) {
            cur -> next = cur -> next -> next;
            }
            else {
                cur = cur -> next;
            }
        }
        return dummyhead -> next;
    }
};

206 反转链表

这个题目相对容易，使用双指针
cur指向前一个pre，在这里做反向
二者都向后移动
用temp做记录防止丢失
是一个遍历的过程，注意初始化的处理，结束条件的处理

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur != NULL) {
            ListNode* temp = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

707设计链表

这个题费了很多时间，搞了两三天才搞明白
基本上把函数内部的功能搞清楚了，定义结构体还不太懂
get函数，注意cur刚好遍历到index的下标
前插函数，cur指向index前一个
删除函数，cur也指向index前一个
注意写语句的前后顺序

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) {//返回第index个节点的值，节点从0开始计数
        if(index < 0 || index > _size - 1) {
            return -1;
        }
        LinkedNode* cur = _dummyHead -> next;//相当于将cur挂到dummyhead后面，没有明确的head的定义
        while(index--) {
            cur = cur -> next;
        }
        return cur -> val;//这个下标没有问题，第index个节点对应的就是cur自己的值
    }
    
    void addAtHead(int val) {//在头结点之前插入val,
        LinkedNode* newnode = new LinkedNode {val};
        newnode -> next = _dummyHead -> next;//先走第二条边连接，再走第一条边
        _dummyHead -> next = newnode;//这个操作也没有问题，相当于只在dummyhead的地方操作，和后面没有关系
        _size++;
    }
    
    void addAtTail(int val) {//在尾结点之后插入val
        LinkedNode* cur = _dummyHead;
        while (cur -> next != NULL) {
            cur = cur -> next;
        }
        LinkedNode* newnode = new LinkedNode (val);
        //newnode -> next = cur -> next; 新节点的next自动是NULL
        cur -> next = newnode;//这个操作没有问题，cur遍历到最后一个节点，然后在这个之后插入
        _size++;
    }
    
    void addAtIndex(int index, int val) {//在第index个节点前插入，此时cur要指向index之前的一个节点
        if(index < 0) index = 0;
        if(index == 0) index = 0;//在头结点之前插入
        if(index > _size) return;
        if(index == _size) index = _size;//在尾结点之前插入
        LinkedNode* newnode = new LinkedNode (val);
        LinkedNode* cur = _dummyHead;//这个要特别注意，不是next
        while(index--) {
            cur = cur -> next;//特别注意，此时cur向前了一位，指向了index-1，而不是index
        }
        newnode -> next = cur -> next;
        cur -> next = newnode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= _size) return;
        LinkedNode* cur = _dummyHead;//同样注意，提前了一个节点
        while(index--) {
            cur = cur -> next;//注意，cur停在了index前一个
        }
        LinkedNode* tmp = cur -> next;
        cur -> next = cur -> next -> next;
        delete(tmp);
        _size--;
    }
    //输出不懂
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
    //不懂
    private:
        int _size;
        LinkedNode* _dummyHead;
};