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;
}
}
else
prev=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;
else
cur2=cur1->next;
prev1->next=cur1;
prev1=prev1->next;
prev2->next=cur2;
prev2=prev2->next;
}
cur1->next=head2;
return head;
}
};
