您现在的位置是:首页 >技术杂谈 >代码随想录算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表。网站首页技术杂谈

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

Allmight_Q 2024-06-29 00:01:02
简介代码随想录算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表。

LeetCode 203 移除链表元素

题目链接 203.移除链表元素

/**
 * 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* dummyhead = new ListNode(0);//创建虚拟头节点,使对所有节点的删除一致
        dummyhead->next = head;
        ListNode* cur = dummyhead;
        while(cur->next != NULL){
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = tmp->next;
                delete tmp;
            }else
                cur = cur->next;
        }
        head = dummyhead->next;
        delete dummyhead;
        return head;
    }
};

看到题的第一想法

建立虚拟头结点,那么所有结点的删除操作一致

LeetCode 707 设计链表

题目链接 707.设计链表

class MyLinkedList {
public:
    struct LinkNode{
        int val;
        LinkNode *next;
        LinkNode():val(0),next(nullptr){}
        LinkNode(int x):val(x),next(nullptr){}
        LinkNode(int x,LinkNode *next):val(x),next(next){}
    };

    MyLinkedList() {
        _dummyhead = new LinkNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if(index < 0 || index > _size - 1)
            return -1;
        LinkNode* cur = _dummyhead->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkNode* cur = new LinkNode(val);
        cur->next = _dummyhead->next;
        _dummyhead->next = cur;
        ++_size;
    }
    
    void addAtTail(int val) {
        LinkNode* newnode = new LinkNode(val);
        LinkNode* cur = _dummyhead;
        while(cur->next!=nullptr)
            cur = cur->next;
        newnode->next = cur->next;
        cur->next = newnode;
        ++_size;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0 || index > _size)
            return;
        LinkNode* newnode = new LinkNode(val);
        LinkNode* cur = _dummyhead;
        while(index--)
            cur = cur->next;
        newnode->next = cur->next;
        cur->next = newnode;
        ++_size;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index > _size - 1)
            return;
        LinkNode* cur = _dummyhead;
        while(index--)
            cur = cur->next;
        LinkNode* delnode = cur->next;
        cur->next = delnode->next;
        delete delnode;
        --_size;
    }
private:
    int _size;
    LinkNode* _dummyhead;
};

/**
 * 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);
 */

看到题的第一想法

直接码

遇到的困难

  • 对于private和public的理解不到位

看完代码随想录后的想法

  • 在private里定义_size和_dummynode

LeetCode 206 反转链表

题目链接 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* reverseList(ListNode* head) {
        ListNode* dummynode = new ListNode(0);
        dummynode->next = head;
        ListNode* cur = dummynode->next;
        ListNode* latter;
        while(cur->next != nullptr){
            latter = cur->next;
            cur->next = latter->next;//尾插法
            latter->next = dummynode->next;
            dummynode->next = latter;
        }
        head = dummynode->next;
        delete dummynode;
        return head;
    }
};

看到题的第一想法

头插法

遇到的困难

  • Line 18: Char 20: runtime error: member access within null pointer of type ‘ListNode’ (solution.cpp)
    SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:27:20
//头插法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)
            return nullptr;
        //虚拟头结点
        ListNode* dummynode = new ListNode(0);
        dummynode->next = head;
        ListNode* cur = dummynode->next;
        ListNode* latter;
        while(cur->next){
            latter = cur->next;
            cur->next = latter->next;//尾插法
            latter->next = dummynode->next;
            dummynode->next = latter;
        }
        head = dummynode->next;
        delete dummynode;
        return head;
    }
};

//双指针
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *temp;
        ListNode *cur = head;
        ListNode *pre = nullptr;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

//递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr,head);
    }
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == nullptr)
            return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(cur,temp);
    }
};

与第一次代码多了一次head==nullptr的判断,AC了。

看完代码随想录后的想法

  • 还可以用双指针,递归的方法完成
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。