1.链表删除

203. 移除链表元素

循环删除

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

1.如果head节点是空，没有继续的必要了，直接返回

2.删除某个节点的链表是需要其前驱的，因为我们要关联起该节点的前后位置，后面的节点next存储，但是前驱没有啊；以至于我们需要一个prev节点，在下一次循环前将prev指向现在的节点，这样下一次cur的前驱就有了

3.如果是head节点要删除，一定要更新head的位置，我在题中判断的方式是prev是否为空作为cur指向的是否是head的位置

4.当然删除节点要记得释放空间哦~

要逆转一下思维

这个链表的形式不就是单支的二叉树嘛，关键是删除节点还得知道这个节点的前驱，我们可不可以从后往前递归删除啊， 这样我们已经走过上一层，在要删除的位置其实已经可以知道前驱了，那么从后往前的思路应该行得通欸

递归删除

class Solution {
public:void _removeR(ListNode*& head,ListNode* cur, ListNode* prev,int& val){if(cur==nullptr){return;}_removeR(head,cur->next,cur,val);if(cur->val==val){ListNode* tmp = cur;if(prev==nullptr)head=cur->next;elseprev->next=cur->next;cur=cur->next;delete tmp;}return;}ListNode* removeElements(ListNode* head, int val) {_removeR(head,head,nullptr,val);return head;}
};

1.首先如果对链表的递归删除不熟，我们把他可以看成是单支的二叉树，只需要递归一个分支就行了

2.设置cur，prev，val；这里不加引用，因为我们的cur和prev每一层都会更新

3.到底端的判断是cur的指向是否为nullptr

4.我们先要走到最后，所以是先递归后处理，再返回的

5.删除的思想和循环一致

6.要注意的是，我是传了head，并且是引用的；这是因为可能我们的头节点要更新，如果不写头节点位置删除了，头节点也丢失了，所以参数返回了一个head

7.那么要更新head节点的条件也很简单，只要prev的指向是空就行，那么更新head=cur->next，完成所有处理条件

8.处理完要返回上层

2.恼人的链表构造

707. 设计链表

没什么好说的，注意前提条件就行

class MyLinkedList {
public:struct Listnode{int val;struct Listnode* next;Listnode(int val):val(val),next(nullptr){}};MyLinkedList() {head=new Listnode(0); //头节点_size=0;}int get(int index) {if (index > (_size - 1) || index < 0) return -1;Listnode* cur = head->next;while(index--){cur = cur->next;}return cur->val;}void addAtHead(int val) {Listnode* newNode = new Listnode(val);newNode->next = head->next;head->next = newNode;_size++;}void addAtTail(int val) {Listnode* newNode = new Listnode(val);Listnode* cur = head;while(cur->next){cur=cur->next;}cur->next=newNode;_size++;}void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;  Listnode* newNode = new Listnode(val);Listnode* cur = head;while(index--){cur=cur->next;}newNode->next=cur->next;cur->next=newNode;_size++;}void deleteAtIndex(int index) {if (index >= _size || index < 0) return;Listnode* cur = head;while(index--){cur=cur->next;}Listnode* tmp = cur->next;cur->next=cur->next->next;delete tmp;_size--;}
private:Listnode* head;int _size;
};

3.反转链表

206. 反转链表

三指针反转

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* cur = head;if(cur==nullptr)return head;ListNode* next = head->next;if(next==nullptr)return head;while(next){cur->next=prev;prev=cur;cur=next;next=next->next;}cur->next=prev;head=cur;return head;}
};

1.由于是三个指针，prev先指向nullptr，cur指向head，next指向head的next；不过之中有一些判断，不然会出现非法访问

prev优先指向nullptr，没有什么条件的

cur指向head，如果head为空，下面的执行都无意义了，那就直接返回head就行

next指向head的next，如果next为空，只有一个节点，也不需要反转，所有也返回head就行

2.之后循环看的都是next是否为空，之所以不是判断next的下一个为空，是因为我们要尽可能反转多个节点，这样最后剩下的操作会更少

3.到这一步就是在循环中，到底是先执行还是先往后走，我们认为是先执行，执行cur的下一个，由于知道prev，所以cur指向prev就行，再更新所有往后一位即可

4.到这里就是循环结束了，此时next执行空了，但是cur还有值，所以一定要将cur的下一个指向prev，当然我们要返回的是head，以至于我们把head也更新成cur就可以了

依然逆转一下思维

我们根据第一题知道其实递归可很简单的得到前驱，所以递归在这题仍然适用 

递归反转

class Solution {
public:void _reverseR(ListNode*& head,ListNode* cur,ListNode* prev){if(cur->next==nullptr){head=cur;head->next=prev;return;}_reverseR(head,cur->next,cur);cur->next=prev;return;}ListNode* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;_reverseR(head,head,nullptr);return head;}
};

1.在递归外先判断一些不适合进入到递归的形式，比如头节点为空，链表只有一个这些形式

2.递归内，到末端的条件判断，就是cur的next是否为空，因为我们要更新头节点的位置，所以不能是cur为空；更新head，head的next也要更新指向prev

3.先递归到底端，所以先递归再执行反转

4.反转的思路就更加简单了，只要把cur的next指向prev就行，随后返回上层