1.链表重复节点删除

82. 删除排序链表中的重复元素 II

前后指针实现

1.做这道题最大的感受就是：不要觉得开辟空间浪费，多用临时变量去记录。越精确越容易成功

2.首先没有节点或者一个节点直接返回

3.因为头部会出现一样元素的情况，以至于我不认为直接在head上改变是一个很好的选择，所以我重新构建了一个节点作为临时头节点，它用来标记我们需要改变的链表

4.由于还是老生常谈的删除，依然需要节点的前驱，以至于我们创造了三个标记节点，prev标记在head前也就是ret位置，cur为head，next为head的下一个节点

5.整体的删除思路其实就是让next往下走，所以判断循环结束就是看next是不是空。

6.next往后走，要不要删除就是看跟cur是否一样。其实就两种情况，cur->next就是next，说明此时next没有往后走，说明前后不一样，说明不要删除cur。cur->nex不是next，说明next往后走了，需要删除prev到next之间的所有节点

7.如果需要删除的，那么更新前驱prev->next指向next，因为prev到next之间都删除。后续就是循环删除节点：cur指向的就是删除的节点，那么我们先保存到tmp中，cur往后走，删除tmp，直到cur与next在同一个位置

8.如果是添加，其实很简单，就是前驱prev往后走

9.不管是删除还是添加，我们还要往后遍历，所以cur走到next位置，随后检查cur的下一个是否为空，空了就说明遍历完了，那退出就行；没有，则把next继续赋值为cur->next

10.最后循环结束了，head更新为ret的下一个，是否ret，返回head即可

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;ListNode* ret = new ListNode(0,head);ListNode* prev = ret;ListNode* cur = head;ListNode* next = head->next;while(next){while(next&&cur->val==next->val)next=next->next;if(cur->next!=next){prev->next=next;while(cur==next){ListNode* tmp = cur;cur=cur->next;delete tmp;}} elseprev=cur;cur=next;if(cur==nullptr||cur->next==nullptr)break;next=cur->next;}head=ret->next;delete ret;return head;}
};

依然熟悉的前驱，所以我选择递归

递归实现

1.其实之前我们就讲过递归删除节点的操作了，但是这里最烦的应该有两个点：一个是连续删除节点 二是更新头节点，而且是更新跨度很大。这些就是关键，搞定这些就能成功

2.首先，头节点为空或者只有一个节点就退出，不需要执行任何东西

3.递归函数的参数到底怎么设计是一个值得考虑的问题：因为头节点可能会变，所以要传入一个头节点并且要引用接收；前驱和删除标记点都要，需要有一个cur和prev；删除一个节点后如何告诉上层也要删除呢，我们选择传入一个int类型，0为不删除，1为删除，因为上层要知道，所以我们传入引用的变量

4.进入递归，首先是到底部，cur为空到底，返回。那么其他情况就递归往下走

5.走到递归后，我们需要执行删除：

先不考虑头节点怎么办，我们考虑普通的中间点怎么删除

首先是前驱和现在的数一样，这种我们就要删除cur位置，不过前驱要连接cur的next。然后释放掉该删除的点。

其次，我们删除的操作其实只针对某点，但是我们还想它的前驱也被删除，所以我们需要在cur删除这层把target变为1，告诉上层（也就是这层prev）cur指向也要删除。那么我们大条件就是target为1时也要删除。

不过删除掉一系列相同的节点后，我们要停止删除，那么判断的一句就是prev的值和cur 的值是否一样，一样就给target变为0

6.最后我们要分析头节点位置，如果prev等于nullptr就是到头节点了，我们依然用到target是否为1判断头节点位置是否要删除并且更新，为1，head更新为cur的next，删除该节点。如果不用删直接退出。

class Solution {
public:void _delDupR(ListNode*& head, ListNode* prev, ListNode* cur, int& target){if (cur == nullptr)return;_delDupR(head, cur, cur->next, target);if (prev == nullptr){if (target == 1){head = cur->next;delete cur;}return;}if (target == 1 || prev->val == cur->val){target = 1;ListNode* tmp = cur;prev->next = cur->next;cur = cur->next;if(prev->val!=tmp->val)target = 0;delete tmp; }}ListNode* deleteDuplicates(ListNode* head) {if (head == nullptr || head->next == nullptr)return head;int target = 0;_delDupR(head, nullptr, head, target);return head;}
};

2.双链

​​​​​​328. 奇偶链表

最讨厌这种双指针然后换来换去的

1.空节点，一个节点和两个节点的不需要进行操作，直接返回

2.所以链表至少三个节点，我们给出head1标记单数链表开头也就是head；head2标记双数开头也就是head的next；前驱prev1和prev2都指向当前各自头节点；改动节点cur1和cur2也指向各自头节点

3.先不写循环的终止条件，我们先调整节点；cur1要指向prev2的next，随后cur2是cur1的next；这里就要分析了，cur1的下一个为空怎么办。所以cur2要给两个情况，一个是cur的next为空，cur2为nullptr；一个是cur的next有节点，cur2是cur1的next

4.随后前驱指向对应的调整cur，更新prev

5.我们知道cur2根据cur1定，那么我们其实只定cur1作为判断条件就行，因为链表至少三个数，因此按照上面的逻辑运行下来，cur1->next可能为空，cur1->next->next也可能为空，所以看这里条件即可判断是否停止循环

class Solution {
public:ListNode* oddEvenList(ListNode* head) {if(head==nullptr||head->next==nullptr||head->next->next==nullptr)return head;ListNode* head1 = head;ListNode* prev1 = head;ListNode* cur1 = head;ListNode* head2 = head->next;ListNode* prev2 = head2;ListNode* cur2 = head2;while(cur1->next&&cur1->next->next){cur1=prev2->next;if(cur1->next==nullptr)cur2=nullptr;elsecur2=cur1->next;prev1->next=cur1;prev1=prev1->next;prev2->next=cur2;prev2=prev2->next;}cur1->next=head2;return head;}
};