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）代码实现
首先先实现部分链表反转部分文章来源：https://www.toymoban.com/news/detail-662036.html
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时定义在他的后面，用于反转部分尾部的连接文章来源地址https://www.toymoban.com/news/detail-662036.html
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;
}
到了这里，关于【算法刷题之链表篇（1）】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
