代码随想录day3 leetcode203，707，206，剑指offer 76题，62题

链表基础知识

单链表的定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

不定义构造函数行不行，答案是可以的，C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量，下面我来举两个例子：

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

如何定义一个循环链表

// 单链表
struct ListNode {
    int val;  //节点上存储的元素
    ListNode *next;  //指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {} //节点的构造函数
};        


    ListNode* head = new ListNode(0);
    ListNode* node = head;
    for (int i = 1; i < n; i++) { //把n个数都放进链表中
        node->next = new ListNode(i);
        node = node->next;
    }
    node->next = head; // 链表头尾相连，形成一个环形链

203.移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy=new ListNode();
        dummy->next=head;
        ListNode *cur=dummy;
        while(cur->next != nullptr){
            if(cur->next->val==val){
                cur->next=cur->next->next;
            }else{
                //注意这里一定是else，因为还需要继续判断cur->next->val是否等于val
                cur=cur->next;
            }
            
        }
        return dummy->next;
    }
};

707.设计链表

class MyLinkedList {
public:

    struct Node{
        int val;
        Node* next;
        Node(int x):val(x),next(nullptr){}
    };

    MyLinkedList() {
        dummyhead=new Node(0);
        size=0;
    }
    
    int get(int index) {
        if(index>(size-1)||index<0){
            return -1;
        }
        Node *cur=dummyhead->next;
        while(index){
            cur=cur->next;
            index--;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        Node* newHead=new Node(val);
        newHead->next=dummyhead->next;
        dummyhead->next=newHead;
        size++;
    }
    
    void addAtTail(int val) {
        Node *cur=dummyhead;
        while(cur->next!=nullptr){
            cur=cur->next;
        } 
        Node* tail=new Node(val);
        cur->next=tail;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        //if(index < 0) index = 0;  
        if(index==size){
         addAtTail(val);
          //size++;//不能重复size++
          return;
        }//
         Node *cur=dummyhead;
         while(index--){
             cur=cur->next;
         }
         Node* node=new Node(val);
         node->next=cur->next;
         cur->next=node;
         size++;

    }
    
    void deleteAtIndex(int index) {
         if(index>size-1||index<0){
            return;
        }
        Node *cur=dummyhead;
         while(index--){
             cur=cur->next;
         }
         cur->next=cur->next->next;
         size--;
    }
private:
    int size;
    Node * dummyhead;
};

206.反转链表（经典面试题）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //ListNode* dumhead = new ListNode(0);
        //dumhead->next = head;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* 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 = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

剑指offer 76题(今天蔚来实习笔试题)

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        ListNode* dum=new ListNode(0);
        dum->next=pHead;

         ListNode* fast=pHead;
         vector<int> vec(1200,0);
         while(fast){
            vec[fast->val]++;
            fast=fast->next;
         }

        ListNode* pre=dum;
        ListNode* cur=dum->next;
         while(cur){
            while( cur!=nullptr && vec[cur->val]>1){//防止段错误
                pre->next=cur->next;
                cur=pre->next;
            }
                pre=cur;
                if(cur!=nullptr) cur=cur->next;防止段错误     
         }
         return dum->next;
    }
};

剑指offer 62题 孩子们的游戏(圆圈中最后剩下的数)

class Solution {
  public:
    int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0)
            return -1;
        ListNode* head = new ListNode(0);
        ListNode* node = head;
        for (int i = 1; i < n; i++) { //把n个数都放进链表中
            node->next = new ListNode(i);
            node = node->next;
        }
        node->next = head;  // 链表头尾相连，形成一个环形链

        int k = 0;
        while (node->next != node) {
            node = node->next;//有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友
            k += 1;
            if (k == m - 1) {
                node->next = node->next->next;
                k = 0;
            }
        }
        return node->val;

    }
};