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

做题前知识学习：

循环链表可以用来解决约瑟夫环问题。

“数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。”对于这个问题我有疑问，因为我考研学习到的说其实数组的内存存放也不是连续的，是由索引查找的，只不过看起来时连续的。有没有大佬解释一下，是因为它电脑设置的查找方式不同导致的吗？

删除节点：

在C++里最好是再手动释放这个D节点，释放这块内存。

其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

LeetCode ● 203.移除链表元素

没有考虑到头节点为空的情况，我还以为很简单，这都卡住我了。。。

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *curr=head->next;
    struct ListNode *pre=head;
    while(curr){    //错误代码
        if(head != NULL && head->val == val){
            pre=head=head->next;
        }
        else if(curr->val == val){
            pre->next=curr->next;
        }
        else if(curr->val != val){
            pre=pre->next;
        }
        curr=curr->next;
    }
    return head;
}

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *curr = head;
    struct ListNode *pre = NULL;
    while (curr != NULL) {   //正确代码
        if (curr->val == val) {
            if (pre == NULL) { // 如果当前节点是头节点
                head = curr->next;
            } else {
                pre->next = curr->next;
            }
        } else {
            pre = curr; // 只有当当前节点不被删除时，才更新 pre
        }
        curr = curr->next;
    }
    return head;
}

LeetCode ● 707.设计链表

这题居然都挡住我了。逻辑是简单的，但是就是力扣的提示不太到位，有时候理解不到位。官解居然没有指明一个结构体，其实也还好我自己设置了一个。自己技术有限吧。我今天看了看我这开发都感觉难做，测试吧？大佬求解




typedef struct MyLinkedList{
    int val;
    struct MyLinkedList *next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList *obj=(MyLinkedList*)malloc(sizeof(MyLinkedList));
    obj->next=NULL;
    return obj;
} 

int myLinkedListGet(MyLinkedList* obj, int index) {
    MyLinkedList *curr=obj->next;
    for(int i=0;i<index;i++){
        if(curr==NULL){
            return -1;
        }
        curr=curr->next;
    }
    if(curr){
        return curr->val;
    }else{
        return -1;
    }
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList *temp=(MyLinkedList*)malloc(sizeof(MyLinkedList));
    temp->val=val;
    temp->next=obj->next;
    obj->next=temp;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList *curr=obj;
    while(curr->next){
        curr=curr->next;
    }
    MyLinkedList *temp=(MyLinkedList*)malloc(sizeof(MyLinkedList));
    temp->next=NULL;
    temp->val=val;
    curr->next=temp;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList *curr=obj->next;
    MyLinkedList *pre=obj;
    for(int i=0;i<index;i++){
        if(curr==NULL){
            return ;
        }
        curr=curr->next;
        pre=pre->next;
    }
    if(curr){
        MyLinkedList *temp=(MyLinkedList*)malloc(sizeof(MyLinkedList));
        temp->val=val;
        temp->next=curr;
        pre->next=temp;
    }else{
        MyLinkedList *temp=(MyLinkedList*)malloc(sizeof(MyLinkedList));
        temp->val=val;
        temp->next=NULL;
        pre->next=temp;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    MyLinkedList *curr=obj->next;
    MyLinkedList *pre=obj;
    for(int i=0;i<index;i++){
        if(curr==NULL){
            return ;
        }
        curr=curr->next;
        pre=pre->next;
    }
    if(curr){
        pre->next=curr->next;
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    while(obj != NULL){
            MyLinkedList *tmp = obj;
            obj = obj->next;
            free(tmp);
        }
}

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/

力扣 206.反转链表

这题还是简单，考研复试做过了。但现在来写还是不会，只知道要有三个指针。具体怎么样写不出来，还得看一下思路，我是不是脑子不好呀，但我又安慰自己你能做出来但只不过没有那么快那么有效率。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *pre=NULL;
    struct ListNode *curr=head;
    struct ListNode *temp=NULL;//保存下一个位置
    while(curr){
        temp=curr->next;
        curr->next=pre;
        pre=curr;
        curr=temp;//后移
    }
    head=pre;
    return head;
}

又完成一天，哈哈，有够差劲的