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

（1）题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

（2）方法及思路（一次遍历）

1.我们从指针 prev 指向链表的哑节点，随后开始对链表进行遍历。
2.如果当前 cur与 cur.next对应的元素相同，那么我们就需要将 cur 以及所有后面拥有相同元素值的链表节点全部删除。
3.我们记下这个元素值 ，随后不断将 cur从链表中移除
4.如果cur与cur->next对应的元素不相同，则将prev指向cur所在位置，cur继续往下找。
5.当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 dummy.next即可。
注意：哑节点可以不用考虑head就被删的特殊情况

（3）代码实现

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head==NULL){return NULL;}ListNode* newnode=new ListNode(0);ListNode* prev=newnode;prev->next=head;ListNode* cur=head;while(cur!=NULL&&cur->next!=NULL){if(cur->val==cur->next->val){int val=cur->val;while(cur != NULL && cur->val == val){cur = cur->next;}prev->next=cur;}else{prev=cur;cur=cur->next;}}return newnode->next;}
};

2.leetcode-19. 删除链表的倒数第 N 个结点

（1）题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

（2）方法一：双指针

思路：
1.先定义一个first指针，由于要删掉倒数第n个节点，所以可以让first指针先走n步。
2.当first走完，在定义一个second指针，此时两指针一起走，当first走到尾部时，second就走到了要删掉的节点的前一位。
3.将second所在节点指向它下一位的下一位，即可删掉
注意点：first和second从哪里开始走？first的终止条件是哪里？
first从head出发，终止条件是走到空停止，
而对于second与第一题中一样，引入哑节点，second从此处开始走

代码实现

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* newnode=new ListNode(0,head);ListNode* cur=head;while(n>0){cur=cur->next;n--;}ListNode* prev=newnode;while(cur){prev=prev->next;cur=cur->next;}prev->next=prev->next->next;return newnode->next;}
};

（3）方法二：计算链表长度（最直观）

思路：
一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。
代码实现

class Solution {
public:int getLength(ListNode* head) {int length = 0;while (head) {++length;head = head->next;}return length;}ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);int length = getLength(head);ListNode* cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur->next;}cur->next = cur->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};

（4）方法三：栈

思路：
我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。（也就是只要找到就直接操作）
代码实现

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);stack<ListNode*> stk;ListNode* cur = dummy;while (cur) {stk.push(cur);cur = cur->next;}for (int i = 0; i < n; ++i) {stk.pop();}ListNode* prev = stk.top();prev->next = prev->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};

3.leetcode-83. 删除排序链表中的重复元素

（1）题目描述

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

（2）方法及思路（一次遍历）

思路：具体地，我们从指针 cur\textit{cur}cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同，那么我们就将 cur.next 从链表中移除；否则说明链表中已经不存在其它与 cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。

（3）代码实现

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* cur = head;while (cur->next) {if (cur->val == cur->next->val) {cur->next = cur->next->next;}else {cur = cur->next;}}return head;}
};

4.leetcode-86. 分隔链表

（1）题目描述

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。

（2）方法及思路（模拟）

思路：
直观来说我们只需维护两个链表 small 和 large 即可，small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x的节点。遍历完原链表后，我们只要将 small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。
1.先定义两个哨兵位smallHead和largeHead这样做的目的是为了更方便地处理头节点为空的边界条件。
2.遍历链表，找出小的储存进small，大的储存进large
3.合并链表时注意large节点的指向，并注意要删除largeHead

（3）代码实现

class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* small=new ListNode(0);ListNode* smallHead=small;ListNode* large=new ListNode(0);ListNode* largeHead=large;while(head!=NULL){if(head->val<x){small->next=head;small=small->next;}else{large->next=head;large=large->next;}head=head->next;}large->next=NULL;small->next=largeHead->next;delete largeHead;return smallHead->next;}
};

5.leetcode-25. K 个一组翻转链表（较难）

（1）题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

（2）方法及思路（模拟）

思路：
1.首先按照k来进行分组，每k个会重新是一个head。
2.然后对每k个数进行反转链表。
3.反转完链表，要注意头和尾与前后的相连，所以在实现反转链表的函数中还要返回头和尾
4.遍历到最后时，如果个数少于k就直接返回

（3）代码实现

首先先实现部分链表反转部分

    pair<ListNode*,ListNode*> myReserve(ListNode* head,ListNode* tail){ListNode* prev=tail->next;ListNode* p=head;while(prev!=tail){ListNode* nex=p->next;p->next=prev;prev=p;p=nex;}return {tail,head};}

总体部分实现
1.在每次实现完注意要有个prev在head前，一开始就是哨兵位，prev用来与反转完的部分进行连接。prev更新的位置即使在tail处（新head前）
2.还要定义一个next在反转链表之前，也就是在找到新tail时定义在他的后面，用于反转部分尾部的连接

ListNode* reverseKGroup(ListNode* head, int k) {ListNode* hair=new ListNode(0);hair->next=head;ListNode* pre=hair;while(head){ListNode* tail=pre;for (int i = 0; i < k; ++i) {tail = tail->next;if (!tail) {return hair->next;}}ListNode* next=tail->next;pair<ListNode*,ListNode*> result=myReserve(head,tail);head=result.first;tail=result.second; pre->next=head;tail->next=next;pre=tail;head=tail->next;}return hair->next;}