算法训练营Day 3

203.移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
文章讲解：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
视频讲解： https://www.bilibili.com/video/BV18B4y1s7R9

考察点：链表基础

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dumyHead = new ListNode();
        dumyHead->next = head;
        ListNode* cur = dumyHead;
        while(cur!=nullptr&&cur->next!=nullptr){
            if(cur->next->val==val){
               ListNode* tmp = cur->next;
               cur->next = cur->next->next;
               delete tmp;
            }else{
                cur = cur->next;
            }
        }
        return dumyHead->next;
    }
};

707.设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/
文章讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E4%BB%A3%E7%A0%81
视频讲解：https://www.bilibili.com/video/BV1FU4y1X7WD

考察点：链表基础

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

    MyLinkedList() {
        dumyHead = new LinkedNode(0);
        count = 0;
    }

    int get(int index) {
        if (0 <= index && index < count) {
            LinkedNode *res = dumyHead;
            for (int i = -1; i < index; i++) {
                res = res->next;
            }
            return res->val;
        } else {
            return -1;
        }

    }

    void addAtHead(int val) {
        LinkedNode *newNode = new LinkedNode(val);
        newNode->next = dumyHead->next;
        dumyHead->next = newNode;
        count++;
    }

    void addAtTail(int val) {
        LinkedNode *node = dumyHead;
        LinkedNode *newNode = new LinkedNode(val);
        while (node->next != nullptr) {
            node = node->next;
        }
        node->next = newNode;
        count++;
    }

    void addAtIndex(int index, int val) {
        if (index < 0) {
            addAtHead(val);
        } else if (index == count) {
            addAtTail(val);
        } else if (index > count) {
            return;
        } else {
            LinkedNode *node = dumyHead;
            LinkedNode *newNode = new LinkedNode(val);
            for (int i = 0; i < index; i++) {
                node = node->next;
            }
            newNode->next = node->next;
            node->next = newNode;
            count++;
        }
    }

    void deleteAtIndex(int index) {
        if (0 <= index && index < count) {
            LinkedNode *node = dumyHead;
            for (int i = 0; i < index; i++) {
                node = node->next;
            }
            LinkedNode* tmp = node->next;
            node->next = node->next->next;
            delete tmp;
            count--;
        }
       
    }
    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = dumyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

private:
    int count;
    LinkedNode *dumyHead;
};

206.反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/
文章讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E5%8F%8C%E6%8C%87%E9%92%88%E6%B3%95
视频讲解： https://www.bilibili.com/video/BV1nB4y1i7eL

考察点：链表基础, 双指针

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