单向链表题库2（c++）
目录
- 前言
- [1.力扣——LCR 123. 图书整理 I](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/)
- [2.力扣——LCR 024. 反转链表](https://leetcode.cn/problems/UHnkqh/submissions/580256040/)
- [3.力扣LCR 141. 训练计划 III](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/description/)
- [4.力扣——2487. 从链表中移除节点](https://leetcode.cn/problems/remove-nodes-from-linked-list/)
- [5.力扣——2816. 翻倍以链表形式表示的数字](https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/description/)
- 结语
前言
接着上一个作品的题库，没学单向链表的先看我这个作品（蓝色字体点进去），再看题库1巩固知识，然后再看这个题库。
1.力扣——LCR 123. 图书整理 I
（蓝色字体点进去看原题）
代码题解
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<int> reverseBookList(ListNode* head) {//这一题就是反转链表,也就是逆序输出链表
vector<int> ans;//定义一个顺序表用于返回逆序输出的值
while(head){
ans.push_back(head->val);
head=head->next;
}
int l=0,r=ans.size()-1;//一定要注意顺序表是从下标0开始的所以最后一个下标是长度减一
while(l<r){//逆序输出就相当于对称换值
int t=ans[l];
ans[l]=ans[r];
ans[r]=t;
l++,r--;//l往后跑，r往前跑
}
return ans;
}
};
2.力扣——LCR 024. 反转链表
代码题解
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next)return head;//递归出口，如果链表头结点为空或者只有一个节点就返回head
ListNode*newHead=reverseList(head->next);//newHead用于每层反转链表之后的新头节点
head->next->next=head;//反转链表以后head就不是头结点了是尾结点head->next看做newHead，newhead->next为head
head->next=NULL;//因为head为尾结点所以head->next为空
return newHead;
}
};
3.力扣LCR 141. 训练计划 III
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
if(!head||!head->next) return head;
ListNode*newHead=trainningPlan(head->next);
head->next->next=head;
head->next=NULL;
return newHead;
}
};
4.力扣——2487. 从链表中移除节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
if(!head)return NULL;//递归出口
head->next=removeNodes(head->next);//假定进行递归的时候得到一个单调不增的链表，返回这个链表的头结点
if(head->next==NULL)return head;//然后让head与head->next(单调不增的链表头结点)比较如果head大返回head，反之返回head->next也就是移除了head
if(head->val<head->next->val)return head->next;
return head;
}
};
5.力扣——2816. 翻倍以链表形式表示的数字
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
void doDouble(ListNode*head,int* cap){//cap代表进位的值
if(!head){//递归出口head为空也就是链表到尾部了
*cap=0;//最后一位的进位肯定为0
return ;
}
int val;
doDouble(head->next,&val);
*cap=(2*head->val+val)/10;//记录当前节点的进位
head->val=(2*head->val+val)%10;//记录当前节点翻倍后的值
}
public:
ListNode* doubleIt(ListNode* head) {
int val;
doDouble(head,&val);
return val == 0 ? head : (new ListNode(val,head));//如果val为0也就是说最高位没有进位也就不用生成新的节点，否则生成新的节点保留进位的值返回即可
}
};
结语
看完这几题，如果你还想刷更多有关单向链表的题，就去力扣题库分类查看数据结构单向链表的题，那么单向链表就告一段落了，下一个作品我会讲初级数据结构——栈。
想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家
