找建站公司,织梦高清电影网站模板,葫岛百度seo,网址最新连接查询我用的方法是在leetcode再过一遍例题#xff0c;明显会的就复制粘贴#xff0c;之前没写出来就重写#xff0c;然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了#xff0c;使用leetcode自带的IDE模拟面试环境。
哈希表章节的题目思路很清晰明显会的就复制粘贴之前没写出来就重写然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了使用leetcode自带的IDE模拟面试环境。
哈希表章节的题目思路很清晰主要是C中的写法。
206. 反转链表
如何使用递归解法反转整个 单链表
class Solution {
public:ListNode* reverseList(ListNode* head) {/* 递归解法 */return reverse(head);}ListNode* reverse(ListNode *head){if(head nullptr || head-next nullptr){return head;}ListNode* last reverse(head-next);head-next-next head;head-next nullptr;return last;}
};reverse 函数定义是这样的
输入一个节点 head将「以 head 为起点」的链表反转并返回反转之后的头结点。
原来的链表
[外链图片转存中…(img-KLgVmb78-1696603051839)]
运行完
ListNode last reverse(head.next);
[外链图片转存中…(img-J17okqo4-1696603051839)]
链表变成了这样先不要管递归的压栈的实现细节
[外链图片转存中…(img-d2chnyBs-1696603051840)]
然后运行
head.next.next head;[外链图片转存中…(img-nOEn10VM-1696603051840)]
接下来把head-next指向null并返回现在的头节点last
head-next nullptr;
return last;[外链图片转存中…(img-dQVs9BKX-1696603051840)]
1、递归函数要有 base case也就是这句
if (head NULL || head-next NULL) {return head;
}意思是如果链表为空或者只有一个节点的时候反转结果就是它自己直接返回即可。
2、当链表递归反转之后新的头结点是 last而之前的 head 变成了最后一个节点别忘了链表的末尾要指向 null
head-next NULL;92. 反转链表II
leetcode链接https://leetcode.cn/problems/reverse-linked-list-ii/
给你单链表的头指针 head 和两个整数 left 和 right
其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。 如何反转单链表的一部分这里迭代解法在之前完全反转链表中已经说过了这里重点关注递归法 。
(迭代的思路大概是先用一个 for 循环找到第 m 个位置然后再用一个 for 循环将 m 和 n 之间的元素反转)
25. K 个一组翻转链表
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。k 是一个正整数它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。[外链图片转存中…(img-0ZYveRdG-1696603051840)]
此题见https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/ru-he-k-ge-d591d/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {if (head nullptr) return nullptr;// 区间 [a, b) 包含 k 个待反转元素ListNode *a, *b;a b head;for (int i 0; i k; i) {// 不足 k 个不需要反转base caseif (b nullptr) return head;b b-next;}// 反转前 k 个元素ListNode *newHead reverse(a, b);// 递归反转后续链表并连接起来a-next reverseKGroup(b, k);return newHead;}ListNode* reverse(ListNode* a, ListNode* b) {ListNode *pre, *cur, *nxt;pre nullptr; cur a; nxt a;// while 终止的条件改一下就行了while (cur ! b) {nxt cur-next;cur-next pre;pre cur;cur nxt;}// 返回反转后的头结点return pre;
}
};148. 排序链表
class Solution {
public:ListNode* sortList(ListNode* head) {return sortList(head, nullptr);}ListNode* sortList(ListNode* head, ListNode* tail) {if (head nullptr) {return head;}if (head-next tail) {head-next nullptr;return head;}ListNode* slow head, *fast head;while (fast ! tail) {slow slow-next;fast fast-next;if (fast ! tail) {fast fast-next;}}ListNode* mid slow;return merge(sortList(head, mid), sortList(mid, tail));}ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummyHead new ListNode(0);ListNode* temp dummyHead, *temp1 head1, *temp2 head2;while (temp1 ! nullptr temp2 ! nullptr) {if (temp1-val temp2-val) {temp-next temp1;temp1 temp1-next;} else {temp-next temp2;temp2 temp2-next;}temp temp-next;}if (temp1 ! nullptr) {temp-next temp1;} else if (temp2 ! nullptr) {temp-next temp2;}return dummyHead-next;}
};
