**********

707.设计链表

206.反转链表

总而言之先纪念我第二次自己写这个题目（还是有点丑）

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* i = (ListNode*)malloc(sizeof(ListNode));
    i->next = NULL;
    i->val = -1;
    ListNode* p = i;
    ListNode* j = head;
    while (j != NULL) {
        while (j->val == val && j->next != NULL) {
            j = j->next;
        }
        if (j->val == val) {
            i->next = NULL;
            break;
        }
        i->next = j;
        i = i->next;
        j = j->next;
    }
    return p->next;
}

感觉比之前写好多了，而且想到了前两天学的双指针（没用用好就是了），这次很快就改好了（改了五六次）

突然意识到一个小技巧，关于if和while的选择

（我已经放弃维护规范的代码风格了，那么多空格是在懒得摁，还好有shift+alt+f）

**********

思路：

操作目标节点的前一个节点，使前一个节点的next指针越过目标节点指向下一个正确节点

特殊情况，当目标节点为头结点时，只能将指针head向后移，或者添加虚拟头结点，将真正头结点一般化 （终于向着规范博客文章靠拢了~~）

方法一：分类处理头结点

（代码不比我叨叨管用嘛）

（这是看了卡哥的第一个方法后写的）

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL)
        return head;
    while (head->val == val) {
        if (head->next != NULL) {
            head = head->next;
        } else {
            head = NULL;
            break;
        }
    }
    ListNode* p = head;
    while (p != NULL) {
        if (p->next != NULL && p->next->val == val) {
            p->next = p->next->next;
        } else {
            p = p->next;
        }
    }
    return head;

方法二：创建虚拟头结点

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if (head == NULL)
        return head;
    ListNode*vhead=(ListNode*)malloc(sizeof(ListNode));//创建虚拟头结点
    vhead->val=-1;
    vhead->next=head;//用虚拟头结点连接
    ListNode*p=vhead;
    while(p!=NULL)
    {
        if(p->next!=NULL&&p->next->val==val)
        {
            p->next=p->next->next;
        }else{
            p=p->next;
        }
    }
    return vhead->next;
}

707.设计链表

思路：

有个头结点更好做

(写了三天,终于自己搓出来一个代码啦ε(┬┬﹏┬┬)3)

(还是先纪念我写的代码)

采纳卡尔哥做法，要把delete的也free()掉哦

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

// 创建头结点
MyLinkedList* myLinkedListCreate() {
    MyLinkedList* s = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    s->next = NULL;
    s->val = -1;
    return s;
}

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

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

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList* node = obj;
    while (node->next != NULL) {
        node = node->next;
    }
    MyLinkedList* s = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    s->val = val;
    s->next = NULL;
    node->next = s;
    return;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList* node = obj;
    MyLinkedList* s = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    s->val = val;
    for (int i = -1; i < index - 1; i++) {
        if (node->next == NULL)
            return;
        node = node->next;
    }
    s->next = node->next;
    node->next = s;
    return;
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    MyLinkedList* node = obj;
    for (int i = -1; i < index - 1; i++) {
        if (node->next == NULL)
            return;
        node = node->next;
    }
    if (node->next != NULL)
        node->next = node->next->next;
    else
        node->next = NULL;
    return;
}

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

（我搞不懂力扣上面的官方题解，官方题解上面给出了很多接口里没有的函数，连函数名和给出来的都不一样╰（‵□′）╯，到底闹哪样啊~~！！） （所以就这样吧，会了就是了）

206.反转链表

思路：

遍历所有节点让其next指向前一个节点，最后返回最后一个节点

（之前写过，先纪念自己写的）

（注意末尾的时候要额外连接一下cur和pre）

typedef struct ListNode ListNode;
ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *pre = head, *cur = head, *node = head;
    while (cur->next != NULL) {

        node = cur->next;
        cur->next = pre;
        pre = cur;
        cur = node;
    }
    cur->next = pre;
    head->next = NULL;
    return cur;
}

诶，不对，有个更好的办法（来自卡哥）

方法一：双指针

（虽然但是我用了三个指针，就是把卡尔那里的缓存指针换成了node指针，差不多的）

这里的pre=NULL以及node !=NULL简直太美妙了ヾ(≧▽≦*)o

可以减少很多特判

typedef struct ListNode ListNode;
ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *pre = NULL, *cur = head, *node = head;
    while (node != NULL) {

        node = cur->next;
        cur->next = pre;
        pre = cur;
        cur = node;
    }
    return pre;
}

方法二：递归

有种拿着针穿了好几层布然后一口气把线抻直的快感

typedef struct ListNode ListNode;
ListNode* reverse(ListNode* pre, ListNode* cur) {
    if (cur == NULL)
        return pre;
    ListNode* ans = reverse(cur, cur->next);
    cur->next = pre;
    return ans;
}
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return head;
    ListNode* ans = reverse(NULL, head);
    return ans;
}

（补完一个，啦啦啦✿✿ヽ(°▽°)ノ✿）