[3]-代码随想录算法训练营-day3-链表-part1-526互联

代码随想录算法训练营第二天|链表 part1

1.LeetCode 203.移除链表元素

题目

https://leetcode.cn/problems/remove-linked-list-elements/

思路

遍历，删

两种处理方式，用虚拟头结点、仅用现有连接

刷随想录后想法

思路开拓了

代码编写简洁

实现困难

头结点处理

连续节点处理超时
实现代码
/**
 * 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 *cur, *next = nullptr;
        if(!head){
            return head;
        }

        //头节点为val
        while(head && val == head->val){
            cur = head;
            head = head->next;
            delete(cur);
        }

        //头结点非val
        cur = head;
        while(cur){
            next = cur->next;
            if(next && val == next->val){
                cur->next = next->next;
                delete(next);
            }else{
                cur = cur->next;
            }
        }
        return head;
    }
};
学习收获

处理非头结点时，用else判断cur是否移动

C++释放内存用delete，与之对应的开辟空间用new

LeetCode错误判断及处理

2.LeetCode 707.设计链表

题目
- https://leetcode.cn/problems/design-linked-list/
思路
- 常规思路，使用带头结点的链表
刷随想录后想法
- 节点处理清晰
实现困难
- C++语法问题

实现代码

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

    MyLinkedList() {
        //带头结点的链表
        _dummyHead = new LinkedNode(0);
    }

    int get(int index) {

        int count = 0;
        LinkedNode *cur = _dummyHead->next;
        while(cur){
            if(count == index){
                return cur->val;
            }else{
                count++;
                cur = cur->next;
            }
        }
        return -1;
    }

    void addAtHead(int val) {
        if(_dummyHead){
            LinkedNode *node = new LinkedNode(val);
            node->val = val;
            node->next = _dummyHead->next;
            _dummyHead->next = node;
        }
    }

    void addAtTail(int val) {
        LinkedNode *node = new LinkedNode(val);
        node->val = val;
        node->next = nullptr;

        LinkedNode *cur = _dummyHead;
        while(cur && cur->next){
            cur = cur->next;
        }
        cur->next = node;
    }

    void addAtIndex(int index, int val) {
        int count = 0;
        LinkedNode *cur = _dummyHead;
        //遍历，比对下标
        while(count != index && cur){
            cur = cur->next;
            count++;
        }
        if(count != index){
            //如果遍历完了，仍然没找到索引，说明超标了
            return;
        }else if(cur){
            LinkedNode *node = new LinkedNode(val);
            node->val = val;
            node->next = cur->next;
            cur->next = node;
        }
    }

    void deleteAtIndex(int index) {
        int count = 0;
        LinkedNode *cur = _dummyHead;
        while(cur){
            if(count == index){
                break;
            }else{
                cur = cur->next;
                count++;
            }
        }
        if(count == index && cur && cur->next){
            LinkedNode *delNode = cur->next;
            cur->next = delNode->next;
            delete delNode;
        }
        return;
    }
private:
    LinkedNode* _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);
 */

学习收获
- 关于指针：使用前必须判断该指针是否为空

3.LeetCode 206.反转链表

题目
- https://leetcode.cn/problems/reverse-linked-list/
思路
- 建一个revHead没
- 按head链表顺序读，读一个移动一个节点到revHead后，头插法
- 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* reverseList(ListNode* head) {
        ListNode* revHead = new ListNode(0);
        revHead->next = nullptr;
        ListNode* cur;
        while(head){
            cur = head;
            head = head->next;
            cur->next = revHead->next;
            revHead->next = cur;
        }
        return revHead->next;
        }
};

学习收获