本文主要是介绍复习Day11:链表part04: 206. 反转链表、92. 反转链表II、25. K 个一组翻转链表、148. 排序链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
我用的方法是在leetcode再过一遍例题,明显会的就复制粘贴,之前没写出来就重写,然后从拓展题目中找题目来写。辅以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;}
};
这篇关于复习Day11:链表part04: 206. 反转链表、92. 反转链表II、25. K 个一组翻转链表、148. 排序链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!